Re: MPS: marker-vector

[Helmut Eller <eller.helmut@gmail.com>]

On Mon, Aug 05 2024, Pip Cet wrote:

>> This replaces the vector-with-free-list by a growable vector, i.e. the
>> free entries are always kept at the end of the vector.
>
> I don't think that's entirely accurate; it's quite possible for an entry
> at the beginning of the array to be splatted and remain untouched until
> the next time a DO_MARKERS reaches it, which may take a long time.

Indeed, that's true.

> I see one somewhat theoretical problem with this patch: if a marker is
> simultaneously kept in a weak hash table, it's possible for it to be
> splatted from the marker vector while remaining in the weak hash table
> (there's no guarantee all references will be splatted at the same time);
> if it is then retrieved from the weak hash table and made to point
> nowhere, we will try to remove it from the marker vector, and hit the
> igc_assert.

Never thought about this.  Hm.  I think MPS could easily guarantee that
all references are splatted at the same time: we could think of
splatting a reference like moving an object to address zero.  MPS
certainly guarantees that all references to a moved object are updated
before they are seen by user code.  MPS could do the same for splatted
references.

> The rest of my comments are tiny nits, really:
>
> - capacity isn't redundant on 32-bit systems

Not sure what you mean.  Certainly igc_header_nwords works on 32-bit
systems too; and igc_header_nwords is pretty much the same as capacity.

> - I'd prefer the marker index to be signed; if it is unsigned, we
> don't need to assert it's >= 0, and assigning -1 to it confused me...

You'd have to talk to the person who designed the struct Lisp_Marker.

> - you shouldn't compare Lisp_Objects with ==
> - I'd prefer checking for splatted elements before deciding to grow
> the vector, if we can do so efficiently

Good idea.

> - I find XFIXNAT easier to read when the number is guaranteed to be nonnegative
> - using alloca is problematic for large vectors (which shouldn't be
> dumped, thus a nit)

Probably.

> I wonder whether it wouldn't be faster, upon encountering a marker that
> has been splatted, to fix the entire array all at once. That would
> ensure that creation order is respected, and splatting is relatively
> rare (and, when splatted, we can expect most of the array to have been
> splatted; indeed, I suspect it'd be best to give up on the marker vector
> and build a new one so the old one can be collected and we don't have to
> worry about never shrinking it).

Possibly.  But I also decided to ignore the issue and happily let
somebody else come up with a benchmark that shows that any of this
matters.