Re: MPS: dangling markers

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

>>     36.34%  emacs         emacs                                          [.] igc_remove_marker
>>     35.77%  emacs         emacs                                          [.] igc_add_marker

I don't understand this:

- Why is `igc_remove_marker` slower than `unchain_marker`?
  `unchain_marker` is also O(N), but should have a worse constant
  because of the linked-list structure suffering much more from
  memory latency.

- Why does `igc_add_marker` take as much time as `igc_remove_marker`?
  `igc_add_marker` only needs to find an empty spot (whereas
  `igc_remove_marker` needs to find the one and only spot that holds
  the marker), so while it's also O(N) in the worst case, it should be
  faster on average.

[ FWIW, I'm incidentally playing with an implementation of the "set of
  markers" as an ordered array-with-gap, so bytes<->chars conversions
  take O(log N) time for N markers, because we can use binary search.
  Removal and addition of a marker can also use the binary search to
  find the spot, tho it's still O(N) overall because of the need to move
  the gap, but hopefully the gap is usually nearby already (and the
  constant is much smaller because it's just a `memmove`).
  Mostly fighting with the pdumper now.  ]


        Stefan