Re: MPS: marker-vector

[Pip Cet <pipcet@protonmail.com>]

"Helmut Eller" <eller.helmut@gmail.com> writes:

> What would you think about changing the marker-vector-with-free-list to
> a mundane growable array like in the patch below?

> The main motivation for this would that we could then iterate in
> reverse, or more precisely, in an order that is more like the order used
> for the linked-list-of-markers.  This is relevant for the heuristic in
> buf_charpos_to_bytepos that creates a temporary marker; it works better
> if those temporary markers are visited first.

Thanks for investigating this! I finally understand why the current MPS
code is slower now, I think.

I wonder whether we couldn't reuse more of the weak hash table code for
this, though...

> This replaces the vector-with-free-list by a growable vector, i.e. the
> free entries are always kept at the end of the vector.

I don't think that's entirely accurate; it's quite possible for an entry
at the beginning of the array to be splatted and remain untouched until
the next time a DO_MARKERS reaches it, which may take a long time.

I see one somewhat theoretical problem with this patch: if a marker is
simultaneously kept in a weak hash table, it's possible for it to be
splatted from the marker vector while remaining in the weak hash table
(there's no guarantee all references will be splatted at the same time);
if it is then retrieved from the weak hash table and made to point
nowhere, we will try to remove it from the marker vector, and hit the
igc_assert.

The rest of my comments are tiny nits, really:

- capacity isn't redundant on 32-bit systems
- I'd prefer the marker index to be signed; if it is unsigned, we don't need to assert it's >= 0, and assigning -1 to it confused me...
- you shouldn't compare Lisp_Objects with ==
- I'd prefer checking for splatted elements before deciding to grow the vector, if we can do so efficiently
- I find XFIXNAT easier to read when the number is guaranteed to be nonnegative
- using alloca is problematic for large vectors (which shouldn't be dumped, thus a nit)

> Using Stefan's elb-bytechar benchmark, I get for the
> linked-list-of-markers:
>
>   | test                   || tot avg (s) | tot avg err (s) |
>   |------------------------++-------------+-----------------|
>   | bytechar               ||       11.80 |            0.00 |
>   | bytechar-100k          ||       11.85 |            0.00 |
>   | bytechar-100k-nolookup ||        9.19 |            0.00 |
>   | bytechar-100k-random   ||       16.73 |            0.02 |
>   | bytechar-100k-rev      ||       11.86 |            0.00 |
>   | bytechar-10k-random    ||       12.36 |            0.01 |
>   | bytechar-1k-random     ||       11.93 |            0.00 |
>   | bytechar-nolookup      ||        9.15 |            0.00 |
>   |------------------------++-------------+-----------------|
>   | total                  ||       94.88 |            0.02 |
>
> for the vector-with-free-list:
>
>   | test                   || tot avg (s) | tot avg err (s) |
>   |------------------------++-------------+-----------------|
>   | bytechar               ||       11.63 |            0.01 |
>   | bytechar-100k          ||       11.91 |            0.37 |
>   | bytechar-100k-nolookup ||        8.80 |            0.01 |
>   | bytechar-100k-random   ||      248.07 |            3.84 |
>   | bytechar-100k-rev      ||       11.71 |            0.02 |
>   | bytechar-10k-random    ||       35.24 |            0.53 |
>   | bytechar-1k-random     ||       14.01 |            0.06 |
>   | bytechar-nolookup      ||        8.69 |            0.13 |
>   |------------------------++-------------+-----------------|
>   | total                  ||      350.06 |            3.89 |
>
> and for the growable array:
>
>   | test                   || tot avg (s) | tot avg err (s) |
>   |------------------------++-------------+-----------------|
>   | bytechar               ||       11.34 |            0.08 |
>   | bytechar-100k          ||       11.59 |            0.47 |
>   | bytechar-100k-nolookup ||        8.78 |            0.12 |
>   | bytechar-100k-random   ||       16.17 |            0.33 |
>   | bytechar-100k-rev      ||       11.31 |            0.03 |
>   | bytechar-10k-random    ||       11.76 |            0.01 |
>   | bytechar-1k-random     ||       11.34 |            0.08 |
>   | bytechar-nolookup      ||        8.70 |            0.09 |
>   |------------------------++-------------+-----------------|
>   | total                  ||       91.00 |            0.61 |

Hard to argue with those numbers :-)

I wonder whether it wouldn't be faster, upon encountering a marker that
has been splatted, to fix the entire array all at once. That would
ensure that creation order is respected, and splatting is relatively
rare (and, when splatted, we can expect most of the array to have been
splatted; indeed, I suspect it'd be best to give up on the marker vector
and build a new one so the old one can be collected and we don't have to
worry about never shrinking it).

Pip