Re: Markers in a gap array

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

On Thu, Jul 18 2024, Stefan Monnier wrote:

>> 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.
>
> Hmm... I wonder why there is such a large difference for markers created
> in a random-order compared to the cases where they're created beg-to-end
> and end-to-beg.  My crystal ball is of no help but suggests that it
> might hint at the fact that it's probably a silly effect that could be
> fixed easily once diagnosed.

One problem with the benchmarks is that they all use the same buffer and
that the markers for the previous benchmark can still linger around.
The benchmark driver calls garbage-collect before running a benchmark
and for the old GC that may be enough to collect all the old markers;
with MPS, the old markers are definitely still there.

If I create a fresh buffer for each benchmark, the times of the MPS and
non-MPS version are much closer.

>> Maybe because the vector only grows and never shrinks.
>
> But why would that only show up when the order is random?

To figure out what is going on I run bytechar-100k followed
bytechar-10k-random; in GDB I interrupted the benchmark and printed the
marker array.  After index 100000, it contains suspicious duplicates:

  ...
  (99997 9899604)
  (99998 9899703)
  (99999 9899802)
  (100000 9899901)
  (100001 7272795)
  (100002 7272795)
  (100003 8017474)
  (100004 8017474)
  (100005 7087003)
  (100006 7087003)
  (100007 4076094)
  (100008 4076094)
  ...

The first element is the array index and the second is the charpos of
the marker.  Then I set a breakpoint in build_marker and got this:

#0  build_marker (buf=0x7fffe46c9a10, charpos=6001308, bytepos=6003108)
    at alloc.c:4191
#1  0x00005555557be1a7 in buf_charpos_to_bytepos
    (b=0x7fffe46c9a10, charpos=6001308) at marker.c:238
#2  0x00005555557bf184 in set_marker_internal
    (marker=0x7fffe5a0f4dd, position=0x16e4a72, buffer=0x0, restricted=false)
    at marker.c:587
#3  0x00005555557bf2a3 in Fset_marker
    (marker=0x7fffe5a0f4dd, position=0x16e4a72, buffer=0x0) at marker.c:630
#4  0x00005555557bf640 in Fcopy_marker (marker=0x16e4a72, type=0x0)
    at marker.c:788

It looks like Fcopy_marker calls (indirectly) buf_charpos_to_bytepos and
that creates another marker at the same position (0x16e4a72 is the
fixnum for 6001308).  I doubt that this is intentional, but it may not
be a serious problem.

So why does the problem only show up for random positions?  Maybe
because the benchmark is spending most of the time not in
re-search-forward, but in copy-marker and for random positions the
caching is ineffective?