> I made two assumptions for my test implementation of COW strings:
Wow, you already have a COW implementation? Great to hear!
> 1) we need to be able to share substrings as well as complete strings
> 2) COW must survive garbage collection
> Without these two, I believe the overhead probably outweighs the
> benefits
COW can in certain cases, *not* survive garbage collection, specifically
if there used to be two pointers to the buffer (and it was COW), but now
there is only one (and should not be COW). The implementation you describe
below seemed to handle this case, but your 'assumptions' above seem to
say that it does not handle this? What did I miss?
> 1) The string header has to reference both the start of the buffer and the
> start of the string i.e. we need to add either a second pointer or an
> offset. This impacts on all code using bufstart as the start of the string.
Yeah, I but I believe this is fine. The impact on string size is just 4
bytes. We already have bufused (buflen), so we need abufbegin (bufstart).
I wonder what the Perl5 implementation overhead on strings is?
> 2) Some sort of flag or counter is required during garbage collection to
> ensure that a given buffer is only copied once. Since the current version of
> Parrot_allocate always makes the buffer larger than the requested size, I
> just used the byte after buflen. To make sure I always have space for the
> relocation address, I changed string_make to round the buffer size up to one
> less than the next multiple of 16; _allocate will then go one bigger, which
> will be the flag byte.
Ahh, nice. In my few minutes of thinking about it, I got stuck wondering
how to store information that belongs to the buffer data (the refcount,
for example).
This kind of hidden data needs to be documented. Perhaps we should define
a buffer-header struct (oh, wait, that name's taken) that we can put at
the head or tail of a buffer for this kind of data.
> The flag byte needs three values:
> a) Uncopied buffer (set when buffer is allocated)
> b) Copied once, not referenced again
> c) Copied once and referenced by at least one other header
>
> I was originally thinking of a separate pass to find buffers in state (b)
> and reset their (header's) COW flag; an alternative would be to store the
> address of the first header in the old buffer (need to ensure that a
> minimum-size buffer can hold two pointers as well as the flag byte!) and
> clear its COW flag regardless; if another reference to the same buffer is
> found, then set the COW flag in the first header. This removes the second
> pass at a slightly increased cost for the normal GC pass.
I like the second idea, but I'm a bit confused on how you're implementing
it. The one I see, but I'm not sure is the one you described, requires a
loop at the beginning of do_collect to set the buffer's seen_already to 0,
and the buffer_header's COW to 0. Then, as we go through the real copying
of the buffers:
-If seen_already is zero, we set the pointer in the buffer to point to our
buffer header.
-If seen_already is one, we follow the stored pointer back to the orig
buffer, set COW to one on it, and set COW to one on our own buffer.
This implementation requires a single bit for the buffer flags, and one
extra pointer (as opposed to the two you mention). It unfortunately, also
has an extra loop overhead in do_collect.
Can you clarify how yours works a bit more, please? Does yours do anything
in do_dod_run, or is it all in do_collect ("GC pass" was unspecific, at
least to me). I don't see where the two two pointers come from, or why you
need three values in your flag byte, and thus I have no idea how yours
works. :)
> Before Dan put his memory allocation / garbage collection system in place,
> COW gave a significant performance increase on string-intensive processing,
> due to the overheads of using the system memory allocator and to the
> ever-increasing memory utilisation. In my latest tests, COW seemed to make
> very little difference; however, I have not yet implemented the clearing of
> the COW flag as discussed above, so "once a cow, always a cow", which will
> have some negative impact.
Well, did you make the necessary changes to the various strings?
Currently, all the string operations are immutable operations, and so COW
won't provide much benefit, unless you fix substring to return the correct
'pointer to the middle of a string, but with COW' string_headers, and so
on. And likewise, make the mutable funcs (of which there is chopn,
currently), to handle COW properly.
Did you handle all that in your test code? Or is it currently benchmarking
functionality which doesn't get executed? :)
Mike Lambert
