Faster sv_utf8_upgrade()

Consider what currently happens when the tokenizer is scanning a string.
It looks through it byte-by-byte until it finds a character that forces
it to decide to go to utf8.  It then calls sv_utf8_upgrade() with the
portion of the string scanned so far.

sv_utf8_upgrade() starts over from the beginning, and scans the string
byte-by-byte until it finds a character that varies between non-utf8 and
utf8.  It then calls bytes_to_utf8().

bytes_to_utf8() allocates a new string that can handle the worst case
expansion, 2n+1, of the entire string, and starts over from the
beginning, and scans the input string byte-by-byte copying and
converting each character to the output string as it goes.

It doesn't return the size of the new string, so sv_utf8_upgrade()
assumes it is only as big as what actually got converted, throwing away
knowledge of any spare.

It then returns to the tokenizer, which immediately does a grow to get
space for the unparsed input.  This is likely to cause a new string to
be allocated and copied from the one we had just created, even if that
string in actuality had enough space in it.

Thus, the invariant head portion of the string is scanned 3 times, and
probably 2 strings will be allocated and copied.

My solution to cutting this down is to do several things.

First, I added an extra flag for sv_utf8_upgrade that says don't bother
to check if the string needs to be converted to utf8, just assume it
does.  This eliminates one of the passes.

I also added a new parameter to sv_utf8_upgrade that says when you
return, I want this much unused space in the string.  That eliminates
the extra grow.

This was all done by renaming the current work-horse function from
sv_utf8_upgrade_flags to be sv_utf8_upgrade_flags_grow() and making the
current function name be a macro which calls the revised one with a 0
grow parameter.

I also improved the internal efficiency of sv_utf8_upgrade so that when
it does scan the string, it doesn't call bytes_to_utf8, but does the
conversion itself, using a fast memory copy instead of the byte-oriented
one for the invariant header, and it uses that header to get a better
estimate of the needed size of the new string, and it doesn't throw away
the knowledge of the allocated size.

And, if it is clear without scanning the whole string that the
conversion will fit in the already allocated string, it just uses that
instead of allocating and copying a new one, using the algorithm I
copied from the tokenizer.  (In this case it does have to finish
scanning the whole string to get the correct size.)  The comments have
details.

It still is byte-oriented.  Vectorization et. al. could yield
performance improvements.  One idea for that is in the comments.

The patch also includes a new synonym I created which is a more accurate
name than NATIVE_TO_ASCII.

1 files changed, 5 insertions, 0 deletions

diff --git a/sv.h b/sv.h
index 43bc541559..9acb84e842 100644
--- a/sv.h
+++ b/sv.h
@@ -1716,6 +1716,10 @@ Like sv_utf8_upgrade, but doesn't do magic on C<sv>
 #define SV_COW_OTHER_PVS	1024
 /* Make sv_2pv_flags return NULL if something is undefined.  */
 #define SV_UNDEF_RETURNS_NULL	2048
+/* Tell sv_utf8_upgrade() to not check to see if an upgrade is really needed.
+ * This is used when the caller has already determined it is, and avoids
+ * redundant work */
+#define SV_FORCE_UTF8_UPGRADE	4096
 
 /* The core is safe for this COW optimisation. XS code on CPAN may not be.
    So only default to doing the COW setup if we're in the core.
@@ -1775,6 +1779,7 @@ mg.c:1024: warning: left-hand operand of comma expression has no effect
 #define sv_pvbyte(sv) SvPVbyte_nolen(sv)
 
 #define sv_pvn_force_nomg(sv, lp) sv_pvn_force_flags(sv, lp, 0)
+#define sv_utf8_upgrade_flags(sv, flags) sv_utf8_upgrade_flags_grow(sv, flags, 0)
 #define sv_utf8_upgrade_nomg(sv) sv_utf8_upgrade_flags(sv, 0)
 #define sv_catpvn_nomg(dsv, sstr, slen) sv_catpvn_flags(dsv, sstr, slen, 0)
 #define sv_setsv(dsv, ssv) \