Re: Markers in a gap array

[Helmut Eller <eller.helmut@gmail.com>]

On Thu, Jul 04 2024, Stefan Monnier wrote:

>> Could you share a more complete recipe for the benchmark? I wonder how it
>> compares to Gerd's weak vector/freelist in scratch/igc.
>
> Put it into the `benchmark` subdir of `elisp-benchmarks` and then do
>
>     emacs --batch -Q -l .../elisp-benchmarks/elisp-benchmarks-autoloads.el \
>           --eval '(elisp-benchmarks-run "bytechar")'
>

The current scratch/igc branch, configured with MPS and -O2
-fno-omit-frame-pointer:

  | test                   || tot avg (s) | tot avg err (s) |
  |------------------------++-------------+-----------------|
  | bytechar               ||       12.11 |            0.18 |
  | bytechar-100k          ||       12.38 |            0.17 |
  | bytechar-100k-nolookup ||        9.14 |            0.22 |
  | bytechar-100k-random   ||      271.52 |           14.27 |
  | bytechar-100k-rev      ||       12.38 |            0.24 |
  | bytechar-10k-random    ||       38.08 |            1.43 |
  | bytechar-1k-random     ||       14.95 |            0.48 |
  | bytechar-nolookup      ||        8.97 |            0.12 |
  |------------------------++-------------+-----------------|
  | total                  ||      379.53 |           14.36 |

and without MPS:

  | test                   || tot avg (s) | tot avg err (s) |
  |------------------------++-------------+-----------------|
  | bytechar               ||       11.42 |            0.03 |
  | bytechar-100k          ||       11.48 |            0.02 |
  | bytechar-100k-nolookup ||        9.15 |            0.00 |
  | bytechar-100k-random   ||       16.39 |            0.02 |
  | bytechar-100k-rev      ||       11.48 |            0.02 |
  | bytechar-10k-random    ||       11.97 |            0.02 |
  | bytechar-1k-random     ||       11.56 |            0.01 |
  | bytechar-nolookup      ||        9.13 |            0.04 |
  |------------------------++-------------+-----------------|
  | total                  ||       92.58 |            0.06 |

So the weak vector doesn't compare very well to the linked list.  Maybe
because the vector only grows and never shrinks.  The idea with the
sorted markers in a gap array would probably avoid the worst of this.  I
wonder why the linked list doesn't seem similar issues.