Re: master 979308b4ca 5/9: org-export-data: Concatenate strings in temporary buffer for performance

[Stefan Monnier <monnier@iro.umontreal.ca>]

Ihor Radchenko [2022-06-16 20:49:27] wrote:
> I hope that I did not get it wrong.  I _believe_ that I did see an
> improvement. So, you better check if it makes a difference on your side
> if you revert that patch (especially with un-optimized build where the
> differences should be more prominent).

The fact that you think you saw a significant difference is already
a good hint that there might be something there, in any case.
But of course, we need to look more closely to see not just "if" but
"how" it is faster.

> AFAIK, there are several caveats with `mapconcat':
> 1. The way it was used in Org before the patch was
>    (mapconcat #function sequence "")
>    Here, `mapconcat' will call `concat' to generate the new string with 2N
>    number of arguments. Half of the arguments will be "".

That's true but we're talking about a single vector, which is allocated
via SAFE_ALLOCA, so it shouldn't put any significant extra pressure on
the GC, and compared to the time taken to do the "map" part of
`mapconcat`, it should be negligible.

This said, it's trivial to eliminate this cost and is probably
a good optimization.  See patch below.

> 2. `concat' is doing ad-hoc save/restore of text properties. IDK if it
>    matters in this particular case, but buffers should work more
>    efficiently with handling text properties (AFAIK)

Indeed, I suspect if there's a performance difference it is likely
coming from that area.

> 3. `concat' tries to consider non-string argument adding some (probably
>    small) extra overheads.

This should be dwarfed by the "map" part of `mapconcat`, so I'd be
surprised if it makes any difference.  Also your replacement code uses
`insert` here instead which performs the same kind of dance anyway.

Lars Ingebrigtsen [2022-06-16 14:45:26] wrote:
> It looks like it shouldn't be that difficult to improve the performance
> radically in the common case of FUNCTION being #'identity.  If there's
> no SEPARATOR we can just pass the arguments more or less directly on to
> Fconcat, and if there is a SEPARATOR, we just have to adjust the arg
> list.

Indeed, we could optimize the common case of function being `identity`,
but it won't help in this particular case.


        Stefan


diff --git a/src/fns.c b/src/fns.c
index d81a3bfcac3..c9251a80f53 100644
--- a/src/fns.c
+++ b/src/fns.c
@@ -2843,12 +2843,18 @@ DEFUN ("mapconcat", Fmapconcat, Smapconcat, 2, 3, 0,
   SAFE_ALLOCA_LISP (args, args_alloc);
   ptrdiff_t nmapped = mapcar1 (leni, args, function, sequence);
   ptrdiff_t nargs = 2 * nmapped - 1;
+  eassert (nmapped == leni);
 
-  for (ptrdiff_t i = nmapped - 1; i > 0; i--)
-    args[i + i] = args[i];
+  if (!NILP (Fequal (separator, empty_multibyte_string)))
+    nargs = nmapped;
+  else
+    {
+      for (ptrdiff_t i = nmapped - 1; i > 0; i--)
+        args[i + i] = args[i];
 
-  for (ptrdiff_t i = 1; i < nargs; i += 2)
-    args[i] = separator;
+      for (ptrdiff_t i = 1; i < nargs; i += 2)
+        args[i] = separator;
+    }
 
   Lisp_Object ret = Fconcat (nargs, args);
   SAFE_FREE ();