Re: [Tcl9-cloverfield] Happy new year!
Status: Alpha
Brought to you by:
fbonnet
From: Frédéric B. <fre...@fr...> - 2009-01-15 14:09:53
|
Hi! ----- "Andy Goth" <unu...@ai...> a écrit : > fre...@fr... wrote: > > Hi Andy! > > It is good to hear from you again. I was worried that you had fallen > off the edge of the earth, or (worse), off the edge of the Internet! Still alive ;-) > > I've had some time to work on my rope thing (as you can read from > the > > message I've just posted) > > I did read it (the email, not the sources), and I am quite excited. > I've been thinking about ropes and whether they're really worth it, > and the conclusion I came to is that they can help performance when > they are implemented as indexes over concatenations of strings of > mixed character width, especially if the strings are mostly contiguous > in memory, such as when they were read from a file. But if the ropes > are "merely" the container, then they negatively impact locality of > reference. Your email agrees with my intuition and backs it up with > both implementation and measurements. Very cool! What you describe sounds like skiplists. OTOH my implementation is "container" based (if I understand what you mean by container), but I get very good performances thanks to the allocator and GC. With the stock allocator I think I'll get the locality problems that you mention. > > > I have some idea for the next stage, AKA the Grand Unification > Scheme of > > string and object structures. > > The ropes I had in mind were actually indexes over arrays of arbitrary > objects. Characters are just one popular type of object. ;^) Yep. There would be no difference between a rope-based string and a btree-based list, aside from memory management: as lists contain objects, they must be traversed as well by a mark-and-sweep GC. But regular operations (insertion, extraction, removal) are identical. I'm certainly going to reuse most of the code I've written on ropes to implement my new lists. Regarding performances, some benchmarking I've run shows a real bonus when handling large objects: while flat allocation (arrays) is algorithmically simpler, allocation of large memory areas take up much more CPU over time because the heap becomes fragmented, and as the memory is non movable the heap is not compactable. This requires very precise strategies (object pools etc.) that can become as complex as writing a custom allocator. Whereas my rope scheme limits the size of contiguous memory blocks to a bit less than a logical page (1KB). This implies that larger data needs to be split into smaller chunks, but in practice the impact is minimal because: - most source data is small: scalar objects, command lines and arguments, etc. - larger data is most often composite - for larger data, random access is O(logn) so the impact of the splitting is limited - traversal is near linear in most case because we can keep contextual info in iterator structures and directly access the leaves that contain actual data Since memory block size is bounded, heap fragmentation is less critical, as large data can be spread over several disjoint blocks. So memory allocation is actually much faster with ropes than with flat lists, which more than compensates for the overhead. Besides, while rope data may be fragmented, memory locality is actually very good because higher order nodes (concat, substr) take up one cell each and thus can be allocated in consecutive cells and fill up holes. For large strings, leaf nodes (those containing char data) take up whole pages, and higher order nodes are allocated next to each other. So traversal benefits greatly from the improved locality (much more than randomly allocated malloc blocks), and for data access there is no different compared to flat strings, since the processor's cache lines don't necessary contain consecutive pages even for flat strings. So in practice flat allocations delegate the algorithmic complexity to the heap allocator. Moreover a tree-based rope means that several ropes can share the same data. This implies that the sum of the lengths of all ropes can far exceed the actually allocated memory. Take a look at Rope_Repeat for example: it can create ropes up to the theoretical limit (4GB) by simply concatenating a rope onto itself, thus consuming a very small amount of memory. Regarding Tcl, this means that the string rep of a container can share a large part of its elements' and take up much less memory than flat strings (besides being faster to allocate and build). Pushing the idea to the extreme, one could build a rope containing ALL the strings of a running app without doubling the memory consumption all of a sudden. Very useful for persistence: build a rope that describes the whole state of the app, dump into file, and restore later. This could provide a feature similar to Smalltalk's VM images. > I made substantial changes to the syntax, to the point of it being > unfair to call my work "Cloverfield". I haven't come up with another > name yet. I warn you: this is all very preliminary, and it's surely > not self-consistent. It's just ideas. > > One major difference is that I backed off completely from the word > modifier idea. I consider dropping some modifiers as well. The whole idea is quite controversial as I found out. [...] > With null gone, I next looked at metadata. I decided to throw it out > as well since its uses can be handled instead by data structures. For > example, I often need multiple pieces of code to track internal > "annotations" they place on common data. They most easily do this by > using the data as the index into an internal associative array. But > with the Cloverfield metadata facility, either only one annotation at > a time is allowed, or every module in an application has to agree on a > convention for not stomping on every other module's annotations. The use case I had in mind for metadata was debugging tools. Metadata is not intended for general or library use. The idea would be that debugging tools could tag values with specific metadata, for example creation context, for later retrieval. As this is a very specific use case I consider reserving the metadata modifier to a debug version, and maybe renaming it to {debug} to be more explicit. But it is a very restricted use case so creating a word modifier is debatable. > I dropped delayed substitution since I can't think of a good use for > it. I got inspired from Lisp's delayed execution. It's very useful in itself but I'll drop it as well if there are other ways to achieve the same purpose, or if it's too difficult to implement. Moreover the semantics needs precise definition, and may need full-fledged closure and/or reference support. > Argument expansion has proven to be very valuable to Tcl, so of course > it stays. But I don't extend it to allow multiple levels of > expansion. I have never seen a case where this would help, and it can > be implemented in script. In Cloverfield it is only extended to be an accepted markup syntax in list string reps. I don't think multiple levels of expansion is useful (not sure what you mean by that). > I really want word comments, but I don't want to think of them as > "word"-anything. Instead I use the more familiar term "inline > comments", and the syntax is #{...}# , where the opening #{ starts > wherever a word can. Braces are matched (modulo embedded quoting), > and it is an error if a # does not immediately follow the final > closing brace. (Note: Vim's syntax highlighter cannot handle nested > comments, so I might have to submit a patch.) My revision will include this syntax as well (dropping the ill-conceived word comments in the process), following a past discussions on this list during which we came to the conclusion that #{ }# should nest so that the following works as expected: #{ if {$cond1} { }# if {$cond2} { ... } This means that sole braces don't match comment openings, inline comments are delimited by complete digrams. > I have a very different idea for references, to be explained below. > But it is not implemented in terms of word modifier notation. > [...] > > On to references! At the moment (I can change my mind in an > instant!), my design actually has two kinds of references. The > difference is in how they are dereferenced. One kind, which somewhat > corresponds to C pointers, requires explicit dereferencing. The > string representation of such a reference is "object 123" or similar. > The other kind, which somewhat corresponds to C++ references, is > dereferenced automatically. The string representation is the > instantaneous value of the referent variable. For now, I name these > "pointers" and "references", respectively. Your references seem close to Cloverfield's. Your pointers seem to be opaque handles like Jim's references. [... more details about pointers and references ...] I don't get all of it but it sounds interesting. Example code welcome! > Miscellaneous: > > - Numbers can be expressed in sexagesimal notation: 12'34'56.78 . ' > is used instead of : to avoid conflict with ?: . I do a lot of GIS > stuff at work, so this would be directly useful to me. It can be used > for time as well as geography. Interesting. Consider also Eiffel-style grouping using underscore, e.g. 1_000_000 is one million. This improves readability a lot. > - Variables, procs, commands, channels, etc. are all in a single > object store, with string pseudo-values "object 123", "command 123", > "channel 123", etc., kind of like in Python. Variables and procs have > proper string representations. [unset] is used to destroy any > reference to an object, and the object is garbage-collected when no > references (e.g. variables) remain. Objects can be local to a stack > frame. Would this allow RAII style programming? > - An object can have multiple representations, not just two. > Non-string conversions may avoid an intermediate string form. > Optimized for common dual-ported case. Hash table used for tracking > multiple representations, and stale representations are removed from > hash table. Hash table created when multiple non-string > representations are valid. Example: taking the list representation of > a dict. I plan the same feature for Cloverfield. I'd suggest using simple arrays or linked lists instead of hash tables, since the number of internal reps would be typically small. A hash table would be overkill for that IMHO. > - Word origins are tracked and accessed with [info origin]. This > facilitates syntax error messages. This would serve the same purpose of Cloverfield's {metadata}. Typically a debug-only feature. > - Variadic and default arguments to proc can appear anywhere in the > argument list, and the "args" argument can have any name; just append > * to denote its catchall status, like in Python. Append ? to the name > to make its default "value" to leave the variable unset. Use a > two-element list to supply a real default value, like in Tcl. Interesting. I like the ? syntax. > And that's what I have so far... Can I steal a couple of ideas? ;-) Cheers, Fred |