Re: MPS: dangling markers

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

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

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.

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

[ 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