COW strings
Implementing COW is a bit harder, although now that we have a DOD pass, a lot easier. We can update counts in there...it's just not very easy to see how we're going to keep track of refcounts. I made two assumptions for my test implementation of COW strings: 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 However, these assumptions then led to a few implementation difficulties: 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. 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. [Incidentally, this makes sense anyway if any in-place string alterations occur, as the otherwise-wasted padding can be used to grow the string] (go_collect currently uses a different rounding rule, which incidentally makes zero-length buffers end up pointing to the same location as the next non-zero length buffer; for COW purposes I changed this to work the same as _allocate) 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. 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. -- Peter Gibbs EmKel Systems
Definition of a null string?
Currently, calling string_make(interp, NULL,0,NULL,0,NULL), as is done by, for example new P0, PerlString, calls Parrot_allocate with a required allocation of zero, which gets converted to 16; a 16-byte buffer is hence allocated, and its address placed in bufstart. However, buflen will still be zero, therefore the block will be discarded as soon as any actual content is assigned to the string. Parrot_go_collect uses a slightly different rounding rule, and will allocate zero bytes to a zero-length buffer; the current allocation address will be placed in bufstart, but the same address will be used for the next buffer collected. Would it be sensible to define 'buflen=0, bufused=0, bufstart=NULL' as a valid null string? This would impact on any code that assumes bufstart to be valid. If not, are there any other suggestions for ways to avoid this proliferation of useless blocks, or should we just let them be created and discarded? -- Peter Gibbs EmKel Systems
[netlabs #482] test seven
# New Ticket Created by Robert # Please include the string: [netlabs #482] # in the subject line of all future correspondence about this issue. sigh. ignore me.
Re: COW strings
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
Re: COW strings
2) COW must survive garbage collection COW can in certain cases, *not* survive garbage collection, specifically The simplest possible implementation of COW strings would be to let the garbage collector 'undo' the COW nature i.e. make multiple copies of all shared buffers. All I meant was don't do this i.e. the GC must understand COWs and handle them appropriately. 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 The extra field is unavoidable, it just means that the patch updates files all over the place, changing 'bufstart' to (in my case) 'strstart'. If COW is going to be implemented, I think that the header change should be made sooner rather than later, as otherwise there will just be more code to change. However, I am not sure what impact the Unicode implementation will have on strings in general. just used the byte after buflen. To make sure I always have space for the 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. I suggested some time ago that we needed a string buffer header as part of the buffer, as distinct from the string header; this was turned down by Dan. My thoughts were that buffer-related information (possibly including things like charset and encoding) could be stored once with the buffer; with COW strings, that would buy us a little bit of memory, on the other hand it is more data to be copied around during garbage collection. So for my version of COW, I cheated and used a hidden trailer. I used the COW flag that already exists in the string header; moving the COW flag to the buffer itself may simplify the GC process, I need to think about that. 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. :) Let me first describe how my current implementation works, without the logic to un-flag ex-COWs: Parrot_allocate sets the hidden flag byte to zero (unseen) when a new buffer is born (this could be done in string_make, but this way nobody outside resources.c needs to know; however, this does mean that non-string buffers get the same treatment). All the other work is done in go_collect. During the copying process, if a header is flagged as COW, and the (old) buffer is flagged as unseen, the address of the new buffer is stored in the old buffer, and the old buffer is flagged as seen. Note that the string start address has to be recalculated to handle substrings (this could be avoided by using an offset, but this would then have to added to bufstart whenever it was used). The new buffer always has its flag byte set to zero, ready for next time around. If a header is COW and the old buffer has been seen already, then no copying is performed; the header's bufstart and strstart are simply updated to point to the new location of the buffer. Thus, we need one pointer in the buffer to hold the relocation address. My current idea for the ex-COW flagging, which I will try to implement today, is as follows. This is slightly revised following your comments, so the use of two pointers has been removed! The first time a buffer is seen, store the header address in the old buffer (I originally thought this would be a second pointer; but it can replace the relocation address since the header already knows that), set the 'seen' flag in the old buffer, and clear the header's COW flag. The second time a buffer is seen, use the pointer to the first header to get the new address of the buffer for updating the second header. Also, set the first header's COW flag (the second header will already be a COW). The three-valued flag is also not required; it does no harm to simply set the first header's COW flag every time. The additional loop you mention is avoided by setting the flag to zero when a buffer is born or copy-collected. Note that the flag we change is the one on the OLD buffer, which is being thrown away as soon as the collection is complete. Well, did you make the necessary changes to the various strings? I changed string_copy and string_substr to make COWs string_concat was changed to work in-place if the first buffer is not COWed and is large enough; the change to string_make to round up buflen means this happens quite often, and is actually a worthwhile optimisation even without COWs. If either of the inputs to _concat is null, it already invokes string_copy and therefore COWs Strangely, string_chopn did not need to change,
Re: Definition of a null string?
On Tuesday 02 April 2002 04:36, Peter Gibbs wrote: Currently, calling string_make(interp, NULL,0,NULL,0,NULL), as is done by, for example new P0, PerlString, calls Parrot_allocate with a required allocation of zero, which gets converted to 16; a 16-byte buffer is hence allocated, and its address placed in bufstart. However, buflen will still be zero, therefore the block will be discarded as soon as any actual content is assigned to the string. buflen should be 16, not 0. bufused should be 0. Parrot_go_collect uses a slightly different rounding rule, and will allocate zero bytes to a zero-length buffer; the current allocation address will be placed in bufstart, but the same address will be used for the next buffer collected. They should probably round the same. Would it be sensible to define 'buflen=0, bufused=0, bufstart=NULL' as a valid null string? This would impact on any code that assumes bufstart to be valid. If not, are there any other suggestions for ways to avoid this proliferation of useless blocks, or should we just let them be created and discarded? Since nothing should be doing validation of the buffer based on bufstart, but only through bufstart via buflen, it shouldn't matter what bufstart's value is - NULL, or a dummy pointer to itself, for instance, if buflen is 0. The question is what should Parrot do when asked to allocate 0 bytes. Since allocating 0 bytes is rather useless, I agree with the rounding up to 16. -- Bryan C. Warnock [EMAIL PROTECTED]
Re: Added macros for interpreter-flags
On Tuesday 02 April 2002 01:48, Josh Wilmes wrote: (apparently the enum type is signed by default). Implementation defined. -- Bryan C. Warnock [EMAIL PROTECTED]
[PATCH] Re: Definition of a null string?
On Tuesday 02 April 2002 04:36, Peter Gibbs wrote:
Bryan C. Warnock [EMAIL PROTECTED] wrote:
buflen should be 16, not 0. bufused should be 0.
Currently, string_make sets the value of buflen. It does not know about
Parrot_allocate's rounding rule, so it uses the supplied size. The patch
below changes string_make to set the allocation request (and hence buflen)
to one less than the next multiple of 16; thus a zero allocation will end up
with a buflen of 15. This looks to be the best that can be done simply.
Parrot_go_collect uses a slightly different rounding rule, and will
allocate
zero bytes to a zero-length buffer; the current allocation address will
be
placed in bufstart, but the same address will be used for the next
buffer
collected.
They should probably round the same.
The patch below changes the GC code to use the same rounding algorithm as
Parrot_allocate i.e. round up to next multiple of 16.
--
Peter Gibbs
EmKel Systems
Index: string.c
===
RCS file: /home/perlcvs/parrot/string.c,v
retrieving revision 1.65
diff -u -r1.65 string.c
--- string.c 30 Mar 2002 03:04:37 - 1.65
+++ string.c 2 Apr 2002 13:24:50 -
@@ -47,13 +47,13 @@
}
s = new_string_header(interpreter);
-s-bufstart = Parrot_allocate(interpreter, buflen);
+s-bufstart = Parrot_allocate(interpreter, buflen | 15);
s-encoding = encoding;
/* Make sure we maintain the flags we might already have on the
* string header we just fetched */
s-flags |= flags;
s-type = type;
-s-buflen = buflen;
+s-buflen = buflen | 15;
if (buffer) {
mem_sys_memcopy(s-bufstart, buffer, buflen);
Index: resources.c
===
RCS file: /home/perlcvs/parrot/resources.c,v
retrieving revision 1.39
diff -u -r1.39 resources.c
--- resources.c 1 Apr 2002 04:35:14 - 1.39
+++ resources.c 2 Apr 2002 13:13:53 -
@@ -727,10 +727,8 @@
interpreter-arena_base-string_header_pool-pool_buffer.buflen);
interpreter-arena_base-string_header_pool-pool_buffer.bufstart =
cur_spot;
cur_size =
interpreter-arena_base-string_header_pool-pool_buffer.buflen;
- if (cur_size 0x0f) {
-cur_size = ~0x0f;
-cur_size += 16;
- }
+ cur_size += 16;
+ cur_size = ~0x0f;
cur_spot += cur_size;
/* Collect the PMC header pool */
@@ -739,10 +737,8 @@
interpreter-arena_base-pmc_pool-pool_buffer.buflen);
interpreter-arena_base-pmc_pool-pool_buffer.bufstart = cur_spot;
cur_size = interpreter-arena_base-pmc_pool-pool_buffer.buflen;
- if (cur_size 0x0f) {
-cur_size = ~0x0f;
-cur_size += 16;
- }
+ cur_size += 16;
+ cur_size = ~0x0f;
cur_spot += cur_size;
/* And the buffer header pool */
@@ -751,10 +747,8 @@
interpreter-arena_base-buffer_header_pool-pool_buffer.buflen);
interpreter-arena_base-buffer_header_pool-pool_buffer.bufstart =
cur_spot;
cur_size =
interpreter-arena_base-buffer_header_pool-pool_buffer.buflen;
- if (cur_size 0x0f) {
-cur_size = ~0x0f;
-cur_size += 16;
- }
+ cur_size += 16;
+ cur_size = ~0x0f;
cur_spot += cur_size;
/* Run through all the buffer header pools and copy */
@@ -772,10 +766,8 @@
string_array[i].buflen);
string_array[i].bufstart = cur_spot;
cur_size = string_array[i].buflen;
-if (cur_size 0x0f) {
- cur_size = ~0x0f;
- cur_size += 16;
-}
+cur_size += 16;
+cur_size = ~0x0f;
cur_spot += cur_size;
}
}
Re: PMCs requiring a 'set' dest register?
On Tue, Apr 02, 2002 at 01:33:59AM -0500, Michel J Lambert wrote: If instead, registers are aliased onto traditional memory variables, such that a PMC pointed to by a register is *also* pointed to by a stash somewhere, then it's a bit harder. I believe this is the desired scheme. Blocking and unblocking dead object detection is probably the simplest way to go. The GC PDD describes the functions to do this, but they aren't implemented. http://dev.perl.org/perl8/pdd/pdd09.pod Making the PMC registers PMC** will make for a lot of overhead even where it is not necessary. -- Jason
Re: [netlabs #482] New Tickets now come to p6i
Ok - New tickets created in the parrot queue on bugs6.perl.org are now automagically sent to p6i. You can just reply to them and the right thing will happen -- the messages will get tracked. Just keep the [netlabs #foo] string in the header. If the tickets don't show up immediately after you've created them, it's probably because they've been sent to moderation. -R (finally making all the pieces happy)
Re: [netlabs #482] New Tickets now come to p6i
could the http://bugs6.perl.org/rt2/Ticket/Display.html?id=XX link be posted in the messages? Robert wrote: Ok - New tickets created in the parrot queue on bugs6.perl.org are now automagically sent to p6i. You can just reply to them and the right thing will happen -- the messages will get tracked. Just keep the [netlabs #foo] string in the header. If the tickets don't show up immediately after you've created them, it's probably because they've been sent to moderation. -R (finally making all the pieces happy) -- Dennis
[APPLIED] core key support
With the following comment: - Changes KEY to contain a KEY_PAIR* instead of a KEY_PAIR** - Changes the MAKE_KEY macro to work within an expression - Changes the MAKE_KEY macro to not return NULL if the value is 0 or NULL. This is needed because an enum_int_val key, for example, will quite often have the value zero, but that shouldn't mean the whole aggregate. I think we'll have to add another macro or a flag for keys with those semantics. But this patch is trying to be the minimum necessary to get PerlArrays working again. - Adds various *_keyed ops to core.ops. This is an incomplete set, because I thought someone might be thinking about autogenerating some of them. This is enough to access command-line parameters and use PerlArrays of PerlInts. - Adds back in the copying of the command-line parameters to P0. - Makes the rx_*group* opcodes work again (they use PerlArrays) - Fixes the array_resize logic. It was totally inconsistent about whether its size parameter was a size or an index, and could seg fault as a result. - Makes array_resize zero out newly allocated memory. This is the only way to tell whether an array slot has been initialized yet. - Sets the PMC GC flags for PerlArrays. - Automatically creates PerlStrings/PerlInts/PerlNums when assigning strings, integers, or numbers to uninitialized PerlArray slots. - Revives the t/pmc/array.t and t/pmc/perlarray.t tests. And as a result, languages/regex is now usable (the test code, in particular, needed key support.) In case you're confused, this patch does *NOT*: - implement the assembler syntax set P0[3], P0[4] (this should be translated to set_keyed_p_kc_p_kc) - automatically generate the *_keyed variants of ops (instead, it explicitly adds a ton of set_keyed and get_keyed op variants in core.ops, and that's not even all that are needed.) - resolve the design gaps for composite keys and whole-PMC _keyed access.
Re: Bugfix release?
On Sat, Mar 30, 2002 at 09:38:31AM -0500, Dan Sugalski wrote: With the recent stack and GC patches, are we pretty much solid now? If so, a 0.0.5 bugfix release may well be in order. -- Everything I wanted to get in to a 0.0.5 release is there now.
Re: [PATCH] Re: Definition of a null string?
On Tuesday 02 April 2002 08:30, Peter Gibbs wrote: Currently, string_make sets the value of buflen. It does not know about Parrot_allocate's rounding rule, so it uses the supplied size. The patch below changes string_make to set the allocation request (and hence buflen) to one less than the next multiple of 16; thus a zero allocation will end up with a buflen of 15. This looks to be the best that can be done simply. Thanks for the patch. However. We should probably have Parrot_allocate (and realloc) actually pass back how much it *really* allocated, as opposed to having to guess and/or reimplement the rounding algorithm everywhere. Either buflen = Parrot_allocate(interpreter, requested_size, bufstart); or bufstart = Parrot_allocate(interpreter, requested_size, buflen); or something else similar. Parrot_go_collect uses a slightly different rounding rule, and will allocate zero bytes to a zero-length buffer; the current allocation address will be placed in bufstart, but the same address will be used for the next buffer collected. They should probably round the same. The patch below changes the GC code to use the same rounding algorithm as Parrot_allocate i.e. round up to next multiple of 16. The above would solve the GC problem, too. A requested reallocation of buflen * 1.2 that also returns a size already rounded to 16 would cause everything to be already aligned, eliminating the need to have to round when walking. Again, it's probably best to bury this within the alloc calls themselves, so that the algorithm is best encapsulated. Thoughts? -- Bryan C. Warnock [EMAIL PROTECTED]
Re: [netlabs #482] New Tickets now come to p6i
Dennis Haney wrote: could the http://bugs6.perl.org/rt2/Ticket/Display.html?id=XX link be posted in the messages? Yes. It should be in all future ones. -R
Re: [PATCH] Re: Definition of a null string?
On 03 April 2002 05:09 Bryan C. Warnock wrote: We should probably have Parrot_allocate (and realloc) actually pass back how much it *really* allocated, as opposed to having to guess and/or reimplement the rounding algorithm everywhere. Either buflen = Parrot_allocate(interpreter, requested_size, bufstart); or bufstart = Parrot_allocate(interpreter, requested_size, buflen); or something else similar. My first thoughts on this are that we should go the whole way, and have Parrot_allocate take a Buffer* and a requested size, and let it fill in the bufstart and buflen parameters (as in the not-yet-implemented Parrot_reallocate patch). This would cause problems for anybody trying to use Parrot_allocate to create temporary storage; however, that is a highly dangerous thing to do anyway without taking the possible impact of GC into consideration. The only place I can find a call to Parrot_allocate that does not place the resulting pointer into a buffer is in the code for 'open' in io.ops. This code is interesting anyway, because it will fail if the second allocate attempt triggers a collection; since this is only for a mode string, the chances are very small, but not zero. Why are we passing a C-style string around inside parrot anyway? -- Peter Gibbs EmKel Systems
Re: [PATCH] Re: Definition of a null string?
At 08:05 AM 4/3/2002 +0200, Peter Gibbs wrote: chances are very small, but not zero. Why are we passing a C-style string around inside parrot anyway? The IO layer is going to be stringified soon. -Melvin
Cola compiler update
Cola now supports conditional expressions in the C#/Java form. See cola/examples/expressions.cola -Melvin
