Re: Markers in a gap array

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

> 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.

> Maybe because the vector only grows and never shrinks.

But why would that only show up when the order is random?

> The idea with the sorted markers in a gap array would probably avoid
> the worst of this.

You could try porting the code in `scratch/markers-as-gap-array`.
I haven't touched it recently, but IIRC the code itself is in reasonably
good shape: the commits themselves need to be improved (better
commit messages, maybe sliced differently) and there's a bit of cleanup
needed around the pdumper code, but it should be reliable enough.

[ I'm still not completely sure if it's a good idea, tho: I mean, I like
  the idea, but the benchmarks aren't very compelling (they're not bad,
  but they're not very enticing either).  ]


        Stefan


PS: BTW, apparently I was confused about XEmacs' markers, they don't use
    a gap-array but a doubly-linked list.  They use a gap-array for the
    extents (where we use a fancier balanced tree instead).
    Also they don't use markers to convert bytes<->chars.
    Instead they keep a (per buffer) cache in an unsorted array of 50 pairs.
    Surprisingly their markers store the bytepos rather than the
    charpos, so `marker-position` always needs to convert to charpos and
    `set-marker` does the other conversion.