Re: [Tcl9-cloverfield] Happy new year!

[Frédéric B. <fre...@fr...>]

----- "Andy Goth" <unu...@ai...> a écrit :

> How will the block size limit impact the extension programmer when
> dealing with large objects?  I guess it will be possible to subdivide
> large objects into smaller objects with some kind of master object
> that points to them.  And arrays (which I find are the main reason why
> objects get to be large) can be handled by this new code you're about
> to write.

Large objects can use contiguous malloc'd blocks wrapped around custom objects, or they can be split into smaller nodes and assembled using a tree (like ropes do with string chunks). In a purely functional, immutable model, the latter is preferable and would give better performances especially because of data sharing and limited memory allocation overhead. Regarding mutability, as I've dropped refcounted objects in favor of a mark-and-sweep GC, the current Tcl solution (using large mutable objects with copy-on-write) is no longer viable, because there is no way to tell whether an object is shared or not, so you have to copy the whole structure every time it's modified, and you end up with an immutable model. For this reason, I believe that a tree with small leaves would perform better on average than large contiguous objects, where random access is only marginally better but memory allocation is much worse.
 
> > - 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
> 
> Can you explain this for me?

Have a look at the iterator code. In short, iterators are stack-allocated structures that store the current iteration context, that is, the leaf node and the local index where iteration takes place plus info about nodes at upper levels. If you iterate over a rope from beginning to end, most operations will then be direct access on the leaf data, with restricted or complete O(logn) tree traversal once in a while. Hence the near-linear complexity.

> > memory allocation is actually much faster with ropes than with flat
> > lists, which more than compensates for the overhead.
> 
> The primary overhead is additional burden placed on the programmer to
> keep everything within size limits.

Indeed. There are two places where extension programmers must take care of size:

 - small objects *should* fit within a single cell as much as possible. While not a strict requirement, it reduces overhead greatly pretty much everywhere as it keeps the heap very compact and allocation is O(1).
 - large objects *must* be split into smaller ones; alternatively, one can still use wrapped malloc'd blocks, or even memory mapping (a strength rather than a weakness).

In real world apps, very few object types would hit the size limit. We will have to provide efficient core types so that extension programmers don't have to build their own. The same way it's done with Tcl lists being used as a generic container. I believe that only very specialized types would be impacted by this limit, and it's also likely that those would already rely on underlying libraries that provide their own structures (matrix calculus for example) in such a way that our ropes/objects only form a wrapping layer around externally managed storage.
 
> The traditional approach is to abstract stuff like this away so that
> the programmer doesn't have to worry about it.  But the costs don't go
> away; they just get hidden and forgotten.  Some of the most
> interesting designs I've seen arose from reëvaluating the historical
> layers of abstraction.  Simple example: simplify the CPU by requiring
> that things be aligned, use the extra die area for registers or cache
> or execution units, and improve the compiler to statically deal with
> alignment.  Basically relocate complexity from a place where it is
> expensive (in the CPU) to a place where it is cheap (in the compiler).

My design is based on the observation that modern architectures are neither limited in computation performances nor in memory size, however the remaining limits are memory throughput and cache size. Hence architectures must make optimal use of cache lines and pagination: memory compacity, locality of reference... My design follows this idea by using a cell-based allocator with very limited overhead (2 bits per cell, i.e. one 16-byte cell per 64-cell pages) compared to a traditional allocator (which uses linked lists of allocated and free space), as well as an allocation policy that favors proximity between related cells. Moreover the mark-and-sweep GC beats simple malloc/free in most cases, even without refcounting (which would add even more space and time overhead), and the generational promotion limits the cache misses even further as well as the impact of GC on stable objects, adding an implicit compaction phase in the process. My preliminary benchmarks make me feel confident about the raw performances I'll get with my implementation compared with traditional architectures (including the current Tcl core).

> > 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).
> 
> Will there be heuristics to decide when to join lots of tiny strings
> into a new array?  If the program concatenates thousands of
> single-character strings, will this be efficient with your current
> rope code?

The current code builds flat strings if the whole data fits into no more than 3 cells. This is a totally arbitrary value that I chose as a compromise between memory consumption and data sharing/duplication.

> set a (0 1 2)
> set b ({*}$a 3 4 5)
> set c {{*}$a 3 4 5}
> puts [lindex $b 0]
> puts [lindex $c 0]
> 
> What will this print?  Pay careful attention to the use of parentheses
> versus braces.

% puts [lindex $b 0]
0

% puts [lindex $c 0]
$a

b is expanded at evaluation time and forms a 6-element list.
c is a 4-element list because "$a" is not a list, i.e. it's a single-element list. Compare with:

% set d {{*}{0 1 2} 3 4 5}
% puts [lindex $d 0]
0


> > I don't think multiple levels of expansion is useful
> > (not sure what you mean by that).
> 
> set a (((0 1) (2 3)) ((4 5) (6 7)))
> set b {*}$a
> set c {*}{*}$a
> 
> would set a to ((0 1) (2 3) (4 5) (6 7)) and b to (0 1 2 3 4 5 6 7).
> 
> But I don't think this is worth having.  The Tcl approach is nice and
> simple.  Just recognize it once.

OTOH multiple levels is just a side effect of allowing expansion within the string rep, not a feature in itself. Moreover, lists with expanded elements are only likely to occur when generating the string rep of a list having expanded references, because other occurrences would be expanded inline. Using the expansion modifier in braced expressions doesn't make much sense in practice unless the programmer is a sado-masochist with a taste for obfuscation.

% set a (0 1)
0 1
% set b ({*}$a 2 3)
0 1 2 3
% set c ({*}$&a 2 3)
{*}{ref .someid}{0 1} 2 3
% lindex $c 0
0
% lindex $c 2
2
% lappend a foobar
% lindex $c 2
foobar

> proc &whatever (a? (b default_value) c d* e?) {
>     if {[info exists &a]} {
>         puts a=$a
>     }
>     puts b=$b
>     puts c=$c
>     puts d=$d
>     if {[info exists &e]} {
>         puts e=$e
>     }
> }
> whatever c
> whatever a c
> whatever a b c
> whatever a b c e
> whatever a b c d1 e
> whatever a b c d1 d2 e

Makes sense. Arguments are expanded in the natural order.

> set &a 1
> set &mydict (alpha &a bravo b charlie &c)
> puts $mydict -> error: reference to nonexistent variable "c"

Late bound weak references.

> puts $mydict(alpha) -> 1
> puts $mydict(bravo) -> b
> puts $mydict(charlie) -> error: reference to nonexistent variable "c"

Ditto.

> Clearly, it's problematic to store references to nonexistent
> variables.  Especially bad is the interactive case, since the shell
> will try to print the string representation of the return value of
> every command, but this is an error for the second [set].  The user
> will think that the error was because [set] failed, but in fact [set]
> succeeded but the shell failed.  I'm tempted to call the whole thing
> off, but references to nonexistent variables are essential, or else it
> would be impossible to ever create a variable in the first place!  So
> I think that shells and interactive debuggers need an alternative to
> taking the string representation, something that breaks down the
> structure a little bit more.  I'm thinking of how Tkcon has "hot"
> errors that can be clicked to get the backtrace.  If the above was
> entered into a program like Tkcon, the displayed return value for the
> second line would be "alpha 1 bravo b charlie _&c_", where _&c_ is
> underlined, in red, and can be clicked for more information.  Tricky
> stuff!  

I've had a similar idea to deal with very long strings. One of my goals is to handle very large datasets transparently and painlessly. For example, imagine building a list containing one element that is a large memory-mapped file. This would take ages to display, especially in an interactive session. Non-interactive apps don't have this problem because they seldom need the string rep of their objects (unless they induce shimmering, which is avoidable). So the idea is to display an abbreviated string with a button to expand the elided part. For example:

% set v [string repeat "0123456789" 10000]
012345678901234567890123456789<... 99940 chars skipped>012345678901234567890123456789

set l (foo $v)
%
foo 01234567890123456789012345<... 99944 chars skipped>012345678901234567890123456789

The idea could be extended not only to strings but to containers as well (lists). So you could apply this concept to errors caused by stale references. 

(Note that Cloverfield avoids this class of problems by design since references always have a valid string rep and a known value in case they are unresolved, although this may change if we allow the string rep generation to fail, as is possible with file backed memory mapping.)

> Now for pointer trickery.  Thankfully, pointers always have string
> representations, even when they point to variables that don't exist
> yet. ;^)

So I get that your @ suffix is syntactic sugar for an explicit pointer dereference.

> Now let me try out the "anonymous references" feature.  Which is
> probably not a good name for it.
> 
> proc &whatever () {return (5 4 3 2 1 0)}
> set &data [whatever]
> puts $data{0} -> 5
> puts $&[whatever]{0} -> 5
> puts $&(5 4 3 2 1 0){0} -> 5
> 
> Look ma, no [lindex]!

Interesting. This allows the variable indexing syntax without an actual variables. Kind of C++ anonymous objects.

> 
> > > - Numbers can be expressed in sexagesimal notation: 12'34'56.78 .
> >
> > Interesting. Consider also Eiffel-style grouping using underscore,
> > e.g. 1_000_000 is one million. This improves readability a lot.
> 
> Are the underscores simply ignored, or are there rules about where
> they can be placed?

Eiffel requires 3-digit groups (i.e. thousands) but a more liberal rule would simply discard them. After all digit grouping is a very cultural matter: Westerners use 3 (a legacy of the Roman empire?), the Chinese and Japanese sometimes use 4-digit grouping, the Indian system uses mixed 2 and 3.

> > > - An object can have multiple representations, not just two.
> >
> > 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.
> 
> Yeah, a short array would probably be a better choice.  There will
> only ever be a handful of valid representations at a time, typically
> just one or two.  Would it be worthwhile to keep the string separate
> from the array of internal representations, or can it be lumped with
> the rest as "just another representation"?  I think I favor the
> latter.  What is the benefit of special-casing the string
> representation?

I'm willing to take the opposite approach: while Tcl defines objects that have a string rep, I'm working on a system where all values ARE strings in the sense that they respond to the string interface, their actual representation being arbitrary (and possibly multiple or layered). This means that you can merge (in the string sense) two "objects" without caring about their actual string rep. In short, objects are ropes. This is one of the big advantages of doing away with the flat strings: in the grand OO tradition, ropes define an interface, not a structure.

> Thanks for taking the time to read my super-long emails.

Hehe! Two brains are better than one.

Cheers, Fred.