Re: MPS: marker-vector

["Gerd Möllmann" <gerd.moellmann@gmail.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.
>
> 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 |
>
> So the results of the growable array and the linked-list-of-markers
> would be closer.  A downside of the growable array is that it needs a
> bit of extra code for the dumper.  I didn't try to port the gap array
> code, because it seems like it would require many more changes and would
> make it even harder to merge with master.

Hm, can't say much about the benchmark, I'm afraid. I've been
successfully ignoring this topic so far :-). I don't even know what the
impact of these numbers in a larger context is.

That said, if you find it important, I trust that, so no objections from
me.

Technically speaking, from reading the diff, I think it's okay. The only
thing I'm wondering about is the compacting of the vector while
iterating over it. I can't put my finger on it, but Is that always safe?

(And I don't know if one can call mps_scan_area without MPS_SCAN_BEGIN/END.)