Re: MPS: dangling markers

[Gerd Möllmann]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

>> Jup, it's point-marker for me. No idea who calls that so often.
>
> I think the core of the problem, then, is that currently it's completely
> normal to rely on the GC to "remove" markers we don't care about any
> more instead of explicitly removing them when we don't need them any
> more (with `move-marker`).
>
> So if the GC takes a long time to call `unchain_dead_markers`, we end up
> with a very large set of markers and it's not clear how to handle that
> efficiently.

Yes.

> I understand that relying on a prompt collection of dead objects is
> a bad idea, but we may have to try and make sure it's prompt enough
> because of the legacy of code which relies on it when it comes
> to markers.

I'm afraid the only way to force MPS to "splat", as they call it, weak
references it by requesting a full collection. Which I think we want
to avoid because that is not done concurrently, the client has to wait
for it to complete.

> If not, we'll have to work at a better data-structure able to handle
> a large set of markers.  The `itree` would probably be our best best but
> if we end up with many markers at the very same place (which seems
> likely if we often call `point-marker`), we'll hit its worst case (where
> it goes back to O(N) tho this N is only the number of markers at a given
> position rather than the total number of markers).

Exactly what I was afraid of after seeing the number of point-markers:
thousands of markers with the same position. And I agree that itree
doesn't help with that, it will degenerate, and we can as well use a
vector then.

I must admit that I'm currently out of ideas.

> [ Another option might be to have a kind of two-level set of markers,
>   where we keep the "recently used" markers in one data structure
>   (optimized for adding/removing/moving/gettingtheposition) and then we
>   demote markers that have not been recently used to a secondary
>   data-structure optimized for "low-cost long term maintenance", kind of
>   a like an archive of markers which are predicted to be dead.  ]
>
> [ BTW, for the bytes<->chars conversion, we could also use a plain array
>   indexed by CHARPOS/CHUNKSIZE where instead of updating the entries
>   upon text insertion/deletion we just truncate the array to the last
>   still-valid entry before the point of insertion/deletion.  ]
>
>
>         Stefan