‘Nonelems’ for pushing sparse array on the stack

To avoid having to create deferred elements every time a sparse array
is pushed on to the stack, store a magic scalar in the array itself,
which av_exists and refto recognise as not existing.

This means there is only a one-time cost for putting such arrays on
the stack.

It also means that deferred elements that live long enough don’t
start pointing to the wrong array entry if the array gets shifted (or
unshifted/spliced) in the mean time.  Instead, the scalar is already
in the array, so it cannot lose its place.  This fix only applies
when the array as a whole is pushed on to the stack, but it could be
extended in future commits to apply to other places where we currently
use deferred elements.

1 files changed, 13 insertions, 0 deletions

diff --git a/av.c b/av.c
index ba97fed31c..f6ffea627b 100644
--- a/av.c
+++ b/av.c
@@ -1015,6 +1015,9 @@ Perl_av_exists(pTHX_ AV *av, SSize_t key)
 
     if (key <= AvFILLp(av) && AvARRAY(av)[key])
     {
+	if (SvSMAGICAL(AvARRAY(av)[key])
+	 && mg_find(AvARRAY(av)[key], PERL_MAGIC_nonelem))
+	    return FALSE;
 	return TRUE;
     }
     else
@@ -1070,6 +1073,16 @@ Perl_av_iter_p(pTHX_ AV *av) {
     }
 }
 
+SV *
+Perl_av_nonelem(pTHX_ AV *av, SSize_t ix) {
+    SV * const sv = newSV(0);
+    PERL_ARGS_ASSERT_AV_NONELEM;
+    if (!av_store(av,ix,sv))
+	return sv_2mortal(sv); /* has tie magic */
+    sv_magic(sv, NULL, PERL_MAGIC_nonelem, NULL, 0);
+    return sv;
+}
+
 /*
  * ex: set ts=8 sts=4 sw=4 et:
  */