[fitz-dev] on enfilades

[Tor Andersson]

Obviously, I forgot to attach the actual log.

On Tue 2003-03-11 00:46:30 +0100, Tor Andersson wrote:
> Hi all.
> 
> This is the first in a series of posts of IRC transcripts of selected
> discussions about Fitz on #ghostscript. I post them here because they
> may be of public interest.
> 
> Enjoy,
> Tor
-------------- next part --------------
[13:17] <maskros> raph: have you thought anymore about separating stream de/encoding into a library?
[13:19] <raph> a little
[13:19] <raph> it's certainly an area of ghostscript i've been wanting to factor out for a whlie
[13:21] <raph> the other major question is what the interface looks like for the stream parameters
[13:21] <maskros> yes. it's highly useful on its own. java has something similar with their input/outputstreams, but the implementations is pretty useless.
[13:21] <raph> we just had a discussion about that this morning - in the case of the jbig2 filter, one parameter is the Globals stream
[13:22] <raph> yeah, the java one has lots of problems
[13:22] <raph> asymmetry between read and write, performance issues
[13:22] <maskros> lack of flush for in/deflaterstreams killed one project....
[13:22] <raph> i did a framework once for general stream processing
[13:23] <raph> (i implemented a web server and some encryption tools)
[13:23] <maskros> ok. how did you solve the parameter issue there?
[13:23] <raph> i didn't
[13:23] <maskros> oh. :(
[13:23] <raph> the creation of streams was just done by C calls
[13:24] <raph> in any case, ghostscript has a reasonably general parameter mechanism
[13:24] <raph> but it's not powerful enough to do jbig2 globals :(
[13:24] <raph> i've certainly given _thought_ to just implementing simple PDF-like objects
[13:25] <raph> names, strings, numbers, arrays, dicts
[13:25] <raph> using simple refcounted memory discipline
[13:25] <raph> so then you could pass a param dict
[13:25] <raph> but i'm not 100% convinced yet that's the best approach
[13:26] <raph> one advantage, though, to that approach is that interop with the python runtime should be pretty simple
[13:26] <maskros> ok. not nice for fitting with plain c, requiring use of another 'runtime' with other datatypes.
[13:27] <raph> { 'Colors': 1, 'BitsPerComponent': 8}
[13:27] <raph> i know
[13:27] <maskros> but the set of types are pretty common... symbols/names/atoms, strings, numbers and lists...
[13:27] <raph> yes
[13:27] <raph> atoms are interesting
[13:27] <maskros> unfortunate that c doesn't provide a one true way of using them...
[13:27] <raph> because i'd _like_ to use an int-like representation
[13:28] <raph> but that means that you have to do some adapter work
[13:29] <raph> it might be good to nail this down now,
[13:29] <raph> because if we _do_ go with this plan,
[13:29] <maskros> and plug in an atom-repository that is application-global. add symbol-tables etc etc
[13:29] <raph> then the same types are almost certainly usable in fitz objects
[13:29] <raph> shadings come to mind
[13:30] <maskros> and to use when parsing pdf.
[13:30] <raph> but again, i'm not sure
[13:30] <raph> it may be that just defining all the appropriate C structures is simpler overall
[13:31] <maskros> that would be more in the spirit of C, and allow for static typechecking.
[13:31] <raph> yes
[13:31] <raph> on the other hand, again python integration is much nicer with dynamic types
[13:31] <raph> and also you don't have to handroll code to serialize and deserialize the objects
[13:31] <raph> (which will be done when writing tree fragments to disk)
[13:32] <maskros> have you looked at ubf?
[13:32] <raph> no
[13:32] <raph> there are a _lot_ of things in that space
[13:32] <maskros> hang on... googling.
[13:33] <raph> http://www.sics.se/~joe/ubf/site/home.html
[13:33] <maskros> http://www.sics.se/~joe/ubf/site/home.html
[13:33] <raph> there's iiop, various xml-based things (ugh), asn.1, bram cohen's bencode
[13:34] <raph> xdr
[13:34] <raph> sexp
[13:34] <maskros> i've only used xml before (ugh), looked at asn.1 (eek), and ignored the rest...
[13:34] <raph> indeed
[13:34] <maskros> ubf looks deviously simple
[13:35] <raph> in any case, i _did_ implement a pdf-objects layer in the first fitz prototype
[13:35] <maskros> it doesn't do dicts, but they can be represented as a-lists (as in ps/pdf)
[13:35] <maskros> i have one in mupdf as well.
[13:35] <raph> the ascii, text representation is not that interesting
[13:35] <raph> you can always use pdf syntax :)
[13:36] <maskros> well, there's that. for fitz trees on disk as well?
[13:36] <raph> i've been thinking much more along the lines of a binary format
[13:36] <raph> because the point of serializing trees is to save space
[13:37] <raph> even so, i expect that these pdf objects would make up a relatively small percentage of the total
[13:37] <raph> i'd totally expect images, fonts, and content streams to dominate
[13:37] <maskros> hm. my experience is that the space tradeoff ascii/binary is fairly small. speed when accessing/searching is more important, and there binary probably wins.
[13:38] <raph> (the latter especially in vector graphics-heavy contexts)
[13:38] <raph> yes
[13:38] <maskros> wouldn't content streams be represented as fitz tree nodes?
[13:38] <raph> if you do things like 4-byte fixed size binary numbers, ascii can actually win on occasion
[13:38] <raph> yes
[13:39] <raph> i shouldn't have included that in the accounting
[13:39] <raph> even so, it's important to look at the space efficiency of serialized tree fragments
[13:40] <maskros> i read some articles about ted nelsons xanadu a while back. some interesting ideas in the enfilades.
[13:40] <raph> i think it's pretty clear that you don't do things like store bboxes, because you can recover them
[13:40] <raph> i read his stuff a long time ago; details are foggy to me now
[13:41] <maskros> bboxes would only be useful for speeding up culling and hit-detection, so you're probably right about not needing to save them on disk.
[13:41] <raph> (you _do_ have a bbox cache, especially for higher-level nodes of the tree; that saves you from having to deserialize tree fragments outside your clip window)
[13:41] <raph> they're surprisingly heavyweight
[13:41] <maskros> you'd probably keep only the bboxes and skip the contents of the nodes.
[13:42] <raph> 64 bytes in libart (double coords)
[13:42] <raph> half that in fitz (32 bit fixed coords)
[13:42] <maskros> 8*4, or do you have non-axis-aligned bboxes?
[13:42] <raph> either way, it's a significant per-node overhead
[13:43] <raph> oops, sorry, i misoverestimated
[13:43] <maskros> ok, so you've decided on 32-bit fixed point math?
[13:43] <raph> 32 bytes in libart, 16 in fitz
[13:43] <raph> yes
[13:43] <maskros> 16.16 precision or 24.8?
[13:43] <maskros> or an unholy hybrid?
[13:43] <raph> 24.8 as default, but set at compile time
[13:44] <maskros> how does that work with default text matrix [.001 0 0 .001]?
[13:44] <raph> the client has to do some work to keep transform matrices in range
[13:45] <raph> much of this work has to be done anyway, because of PDF limits
[13:45] <raph> it wasn't an easy decision, believe me
[13:45] <raph> the simplicity of 64-bit double is quite appealing
[13:46] <raph> but, especially on smaller chips (embedded apps), the cost is too much
[13:46] <maskros> 1/256 is about .004, hardly enough...
[13:46] * maskros thinks floating point math is black magic
[13:46] <raph> ?
[13:47] * raph studied it pretty carefully, way back in the day
[13:47] <raph> had a physics class that focussed heavily on numerical analysis
[13:47] <maskros> wouldn't 1/256 be the smallest possible non-zero number representable with 24.8... or am i way off base here?
[13:47] <raph> yes
[13:47] <raph> and, interpreted as a fraction of a pixel, it ought to be fine
[13:48] <maskros> i haven't gotten around to the numerical analysis courses yet...
[13:48] <raph> for font scaling, you'd do the concatenation of the text matrix and the font scale in double
[13:48] <maskros> double float math also for embedded apps?
[13:49] <raph> yes
[13:49] <raph> but matrix concat is a much rarer operation than rendering
[13:49] <raph> that only happens when you build the tree
[13:49] * maskros remembers trying to run quake on a 486-sx with floating point emulation
[13:50] <maskros> but will the final matrix be accurate enough?
[13:51] <raph> that's a good question
[13:51] <raph> the answer is yes, but some care is needed to make sure
[13:52] <maskros> ok. fair enough. if not, bumping the decimal part a bit or two will have to do :)
[13:52] <raph> heh, yes
[13:53] <maskros> right, where were we? enfilades...
[13:54] <maskros> if i remember correctly, each node in an enfilade has a DSP (displacement) and WID (width) attribute
[13:55] <raph> riiight
[13:55] <raph> that makes updating trickier, you have to walk up the tree
[13:55] <raph> if you have 15 minutes, i'll explain how i'd do it
[13:55] <maskros> and by some trickery, the tree can be mutated without changing the backing store for the data. insert stuff by morphing around nodes above.
[13:56] <raph> i should reread enfilades
[13:57] <maskros> the early stuff was nice, then things got hairy with linking and such. but the basic tree/enfilade was simple and elegant.
[13:57] <maskros> when updating tree, all that is needed is appending to data and changing root node. nice for when the tree is on disk.
[13:57] <maskros> plus you get revision history for free.
[13:57] <raph> yeah, when things go from tree to graph, it gets hairier :)
[13:58] <raph> i have no idea whether i'll implement the full tree-on-disk plan
[13:58] <raph> because i think we can get 90% of the benefit by forcing the client to stick to an append-only access model
[13:59] <raph> and then having intelligent caching on the read side
[13:59] <raph> but here's how it would go:
[13:59] <maskros> tree-on-disk could be useful in a graphics editing program with gigantic models (say, vlsi-prints, etc))
[13:59] <raph> yes
[14:00] <raph> the fundamental model is a b-tree of fixed-size blocks
[14:00] <maskros> could you wait 2 mins?
[14:00] <raph> sure
[14:00] <maskros> gotta get something to chew on...
[14:05] * maskros is back
[14:05] <raph> ok
[14:05] <raph> so the blocks contain a serialization of the tree
[14:05] <raph> you can imagine lisp-style syntax with ( and )
[14:06] <raph> the central idea is that there are two tree-like structures: the b-tree, and the data tree
[14:06] <raph> and there is not necessarily any relationship between them
[14:06] <maskros> ok
[14:07] <raph> so now, at each node, you keep track of a few pieces of meta-info
[14:07] <maskros> b-tree node or data-node?
[14:07] <raph> notably, the overall paren balance, and a "high-water mark" for paren balance
[14:07] <raph> at each b-tree node
[14:07] * raph will try to keep that clear :)
[14:08] <raph> so, start at 0, decrement for each ), increment for each (
[14:08] <raph> the paren balance is the final value, and the high-water-mark is the minimum value across the block
[14:08] <raph> (it's non-positive)
[14:09] <maskros> the high-water-mark would be an indication of depth?
[14:09] <raph> note also that these two values are quite stable wrt (data) tree mutation
[14:09] <raph> no, a _maximum_ value would indicate depth
[14:09] <raph> anyway, continuing...
[14:10] <raph> a tree reference consists of a block id and an offset within the block
[14:10] <raph> these are mostly stable during tree mutation, but not 100%
[14:10] <raph> for example, if you insert stuff within a block, it pushes the offsets of everything that comes after in the same block
[14:10] <raph> consequently, you have to keep track of all your outstanding references into the tree
[14:11] <maskros> (this is where the DSPs of enfilades would help not having to modify the 'tail')
[14:11] <raph> (if you're mutating, that is)
[14:11] <raph> perhaps; i'm not sure
[14:12] <raph> so, if you have one of these node references, you want to be able to efficiently implement the various navigational methods
[14:12] <maskros> back-pointers that will have to be patched when moving a data-node in the b-tree
[14:12] <raph> parent, next sibling, prev sibling, first child
[14:12] <raph> right; the idea is that all references to nodes are in "node reference" objects
[14:13] <raph> which are managed by the tree engine; they are opaque to clients
[14:13] <maskros> on a tangent, have you considered using 'handles' here?
[14:13] <raph> stored in the tree, or for the node references in the api?
[14:13] <maskros> handles as in old mac resources, so the resource manager can move resources without having to backpatch more than one pointer.
[14:14] <raph> these node reference objects are basically the same as handles
[14:14] <raph> yes
[14:14] <maskros> both, i think.
[14:14] <raph> in this design, you don't store handles in the tree
[14:14] <maskros> the mac toolbox had a chunk of mem assigned for this. not sure if they stored handles internally.
[14:15] <raph> anyway, if you look at the navigation algorithms, they're nontrivial but reasonably straightforward
[14:15] <raph> take "next sibling" for example
[14:15] <maskros> would each data-nodes store the ref to its neighbours explicitly?
[14:16] <raph> you might have to skip an arbitrary number of blocks, depending on how much space is taken in the subtree
[14:16] <raph> no; however, that data may be present in a cache
[14:17] * maskros winces.
[14:17] <raph> the paren balance and high-water mark info lets you do that in O(log n) block-retrieve operations
[14:17] <raph> you can go up to the common ancestor, then down
[14:17] <maskros> does the data-node know how deep it is?
[14:18] <raph> no
[14:18] <maskros> so it has to search up through the b-node to find out where it can find its sibling?
[14:19] <raph> yes, in general
[14:19] <maskros> or maybe you should just explain and I shut up...
[14:20] <raph> when you read a b-node, you store it in an "unpacked" representation
[14:20] <raph> probably around 2x the number of bytes
[14:21] <raph> that has extra stuff in it to make navigation fast
[14:22] <raph> caching is pretty critical to the idea
[14:22] <maskros> ok
[14:22] <raph> without it, you get very good space performance, but terrible speed
[14:22] <raph> because you're having to crawl through b-nodes all the time
[14:23] <raph> and if the tree is small, everything fits in the cache :)
[14:23] <maskros> ...unless you are doing a rendering, depth-first through the tree would amount to sequential access of b-nodes as well?
[14:23] *** ghostgum is now known as gg_away
[14:23] <raph> yes, traversal of the tree is reallyfast
[14:24] <maskros> still, i think the idea of implementing caching in c is scary.
[14:24] <raph> you essentially have to cache the path to the current node, so cache size must be at least as deep as the tree
[14:24] <raph> well, if you don't, it still works but performance may be, uh, less than ideal :)
[14:25] <raph> this is a scary chunk of code to implement, yes
[14:25] <maskros> when traversing, the path is implicit on the stack...
[14:25] <raph> that's one way to do it; you can also navigate using just parent and sibling methods
[14:25] <raph> so the only state for the traversal per se is a single node reference
[14:25] <maskros> the tree storage model, would it be pluggable, as the frontends and backends?
[14:26] <raph> that's certainly the idea
[14:26] <raph> the fitz tree api is designed so that you could implement this
[14:26] <maskros> child and sibling you mean?
[14:26] <raph> that and the refcount discipline
[14:27] <raph> when you unref a node, the in-memory representation is allowed to go away
[14:27] <raph> next time you navigate to it, it might be brought back into ram, and you get a different pointer to it
[14:27] <maskros> unref a b-node you mean?
[14:27] <raph> no, a data node
[14:28] <raph> you won't generally be keeping b-nodes in memory
[14:28] <raph> it's better to cache data nodes
[14:28] <maskros> ok. refcounting is internal to tree-storage, and outside access is through ids
[14:28] <raph> yup
[14:28] <maskros> ye, b-nodes is just for quick disk access. that's why they're fixed size.
[14:29] <raph> well, the idea is that the tree engine uses refcounting to know which references are "active" (ie, might be accessed by the client) at any time
[14:29] <maskros> hmm. not sure i get it.
[14:30] <raph> ok, i'll try again
[14:30] <raph> from the point of view of the client, you've got a "node" data structure
[14:31] <raph> the methods implemented on that include parent, next sib, child, etc.
[14:31] <maskros> ok
[14:31] <raph> so when you invoke "next sib" on the node, the tree engine gives you back another node data structure
[14:31] <raph> then, if you unref the first one, the tree engine has the option of freeing it
[14:32] <raph> the key point here is that the reference from a node to its children _doesn't_ count in the refcnt
[14:32] <maskros> ok. so the client unrefs nodes that it won't use anymore. not in the sense of freeing but more as an indication that the client wont touch it for a while?
[14:33] <raph> yes
[14:33] <maskros> there will be explicit api-calls to mutate tree for adding / deleting nodes.
[14:33] <raph> if you call "prev sib" on the second node object, you'll get a node back
[14:34] <raph> it may be the same object as the first one, or it may have been freed and then re-read from disk
[14:34] <raph> yes, all mutation is through the api as well
[14:34] <maskros> then is there a need for refcounts inside the tree at all, or just between the fitz/client interface?
[14:34] <raph> the latter
[14:35] <maskros> is that necessary?
[14:35] <raph> ?
[14:36] <maskros> i mean, if the tree + resources are manually mantained, there is no need for refcounting on that account....
[14:36] <raph> re resources: i'm talking about pure tree, not graph, at this point
[14:36] <raph> i'll have to think about how to best do graph structure
[14:36] <maskros> ...and for clients, if we give them a unique id for each node, we can treat the data nodes in the tree storage as ...
[14:37] <maskros> ...lost my trail of thought there
[14:37] <raph> i think i see what you're saying
[14:37] <raph> yes, using an id is a possibility
[14:37] <raph> but then the tree engine needs to be able to quickly find a given id within the tree
[14:37] <maskros> memory mgmt for trees is unnecessary. refcounting wont help for graphs (if they are possibly cyclic)
[14:37] <raph> it's not impossible, but there is a fair amount of overhead to store all the id's and relationships between them
[14:38] <raph> it's very similar to the way people implement this kind of thing in relational db's
[14:38] <maskros> true. we're talking a lot of nodes. unlike opengl where the number of texture objects and display lists are relatively small.
[14:38] <maskros> but if we use enfilades, a node will have a unique address that wont change even if the tree morphs around in memory.
[14:39] <maskros> still, that requires a full descent at every access and no short-cutting to the node directly.
[14:39] <raph> i'll have to look at enfilades to be able to comment on that
[14:39] <maskros> unless that is also cached.
[14:39] <maskros> ok. how do rdbs do?
[14:39] <raph> it's possible they have a better solution than what i've come up with
[14:40] <raph> basically, you allocate a unique id for each node
[14:40] <maskros> they also talk about tumblers and whatnot i haven't read about in detail. i should try to get his book.
[14:40] <raph> then you have tables for the parent-child and sibling relationships
[14:41] <raph> doing navigation is a query by id, giving you another id
[14:41] <raph> and mutation is typically a transaction involving 2 or 3 table updates
[14:41] <maskros> right. yes. i see what you mean with rdb style.
[14:42] <raph> of course, there are many disadvantages
[14:42] <raph> after extensive mutation, the tree may have little or no locality
[14:42] <raph> which means that a traversal can be pessimally slow
[14:42] <raph> a disk access per node is an eternity
[14:43] <maskros> and for fitz traversal will be by far the most common operation. full-tree or just a small traversal here and another there.
[14:43] <raph> yes
[14:43] <raph> but i think that's common in many applications
[14:43] <raph> first you have to navigate to where you want to go, then you basically want to suck the entire subtree
[14:44] <raph> the inherent locality of the b-tree makes that _nice_
[14:44] <maskros> so for traversing, a traversal ticket that is explicitly used could maybe help?
[14:44] <raph> not sure
[14:44] <raph> maybe
[14:44] <raph> you mean, like an iterator?
[14:44] <maskros> yes. that's the word.
[14:44] <raph> it seems to me that using the generic navigation methods is good enough
[14:45] <raph> but it may be that you can squeeze a bit more optimization out of an iterator
[14:45] <raph> for one, you should be able to evict nodes from the cache more aggressively
[14:45] <maskros> if it's easy caching iterators on the other side, we could get the benefits without the mess of using them.
[14:45] <raph> yeah
[14:46] <raph> so, in any case, this stuff is interesting on-disk,
[14:46] <raph> but where it _really_ gets fun is when you're doing it over a network
[14:46] <raph> and there i think the ideas hold up really well
[14:46] <maskros> oh dear. not only read-access times, but round-trips to worry about as well :(
[14:46] <raph> it's analogous
[14:47] <raph> network roundtrip and disk seek are both really slow operations
[14:47] <raph> in fact, relative to bandwidth, disk seek is even worse
[14:47] <raph> (this is because modern disks have fantastically high bandwidths, in the gigabit/s range now)
[14:48] <maskros> nowadays with 'fast' hard-drives and still slow heads. not to mention cdrom and dvds.
[14:49] <maskros> with cds you have the seek of a wide-area network and the bandwidth of a slow harddrive.
[14:49] <raph> what's appealing is that the network protocol works at b-node granularity, rather than data-node granularity
[14:49] <raph> in fact, you can imagine doing read-only access using a "dumb" server that only knows how to serve byte-ranges
[14:50] <raph> the converse advantage for mutation is in transactions
[14:50] <maskros> yes. or just udp send-me-a-block
[14:50] <raph> you do those with copy-on-write semantics, again at the block granularity level
[14:51] *** ghostgum has joined #ghostscript
[14:51] <raph> similarly for change notification and cache invalidation logic
[14:52] <raph> "tell me when any descendant of this node" changes maps quite cleanly to "tell me when any block in this range of b-nodes changes"
[14:52] <raph> and the latter is fantastically more efficient when batching up lots of updates
[14:52] <maskros> and because it is a b-tree, inserting stuff in the middle only hurts the one node, as opposed to flat file.
[14:52] <raph> ...which, again, you expect to happen with some degree of locality
[14:52] <raph> absolutely
[14:53] <raph> i've been tempted to cook up a simple implementation
[14:53] <raph> but it's not exacltly trivial :)
[14:53] <maskros> mixing trees gives me a headache...
[14:54] <maskros> but it's fascinating to think about.
[14:55] <maskros> how should the change notification info be stored?
[14:57] <raph> ok,
[14:58] <raph> if you imagine a server which has connections open to multiple clients
[14:58] <raph> then a request for a range of blocks gets stored at the common ancestor
[14:58] <raph> ie, you have a mapping here from blocks to 'listeners'
[14:58] <raph> or to lists of listeners, to be more precise
[14:59] <raph> then, whenever you mutate a block, you walk up the tree to the root, and tickle all matching listeners along the way
[14:59] <maskros> ok. this will require an api for the tree-storage to reach out to clients.
[15:00] <raph> ah yes
[15:00] <raph> s/api/network protocol/
[15:00] <maskros> clients that could live anywhere, and could die at any moment.
[15:00] <raph> that distinction is important,
[15:00] <raph> yes because of non-fate-sharing,
[15:00] <raph> and also because of asynchrony
[15:01] <raph> in the time between sending out a change notification and getting a client's response, the tree may have mutated more in the meantime
[15:01] <maskros> so each request will have to be tagged with a timestamp of sorts.
[15:02] <raph> regarding clients dying (and recovery of relevant resources), probably the best inspiration is "leases" from SMB and friends
[15:02] <raph> (SMB has many warts, but the fundamental concept of lease is sound)
[15:02] <maskros> is this (out-of-process-clients) interesting for fitz?
[15:02] <raph> maybe; it's hard to say for sure
[15:02] <raph> not immediately
[15:03] <raph> one context that's particularly intriguing is multiplexing a display between applications
[15:03] <maskros> still, while we're thinking big, the tree-storage could well be useful far outside fitz.
[15:03] <raph> yes, i can definitely think of applications outside fitz for that :)
[15:04] <raph> much of this design work was inspired by dom, which tries to solve somewhat similar problems for the xml infoset
[15:04] <maskros> yes. having a central 'drawing' and multiple parallell editors will make teleconferencing-wieners orgasm :)
[15:04] <raph> exactly; the whiteboard application
[15:04] <maskros> not to be mean to anyone, but w3c seems to fudge things a lot lately.
[15:05] <raph> do not hold back on my account :)
[15:05] <maskros> i could rant forever about html and http and the abuse thereof, but i suspect i'd be preaching to the choir :)
[15:06] <raph> the w3c does a mediocre job on things directly relevant to the web
[15:06] <raph> less good as you start trying to re-use stuff for other applications
[15:07] <maskros> xml+css would be a good starting point for all sorts of wysiwyg editors/wordprocessors/you-name-it
[15:07] <maskros> until you start trying to parse xml, and get css to be specific about fonts :(
[15:08] <raph> yes
[15:08] <raph> the end-user product would be distinctly inferior in lots of important ways, to, say, microsoft word
[15:09] <maskros> and that's not saying a little, given how awful most (all?) word documents look
[15:09] <ghostgum> It's not how they look that bothers me, it's the unpredictable user interface.
[15:10] <maskros> ghostgum: i dont use word, but i do have to read documents written with word...
[15:10] * ghostgum is in a bad mode.  Wireless LAN only half works at home.
[15:10] <ghostgum> s/bad mode/bad mood/
[15:11] <ghostgum> and when it doesn't work, there is no feedback about what is wrong.
[15:11] <maskros> are ed editing commands common on irc elsewhere?
[15:11] <raph> yes
[15:12] <ray_lunch> gg: so what's the problem -- signal strength, link quality, other ?
[15:12] <raph> s// anyway; it's so useful
[15:12] *** ray_lunch is now known as ray
[15:12] <ghostgum> netgear configuration utitilies.
[15:12] <ray> Really ! 
[15:12] * raph became an expert on 802.11b when he set up his network
[15:12] <ghostgum> It appears that if I set the WEP password from the USB utility, it works.
[15:12] <raph> ... and never did get wep to completely interoperate :)
[15:12] <ray> I have a netgear wireless router -- no real problems
[15:12] <ghostgum> But the USB utility can't configure MAC authorisation
[15:13] * maskros wishes he had an airport card
[15:13] <ghostgum> So the SNMP utility can, but if I use it I think the WEP passwords get screwed.
[15:13] <ghostgum> I've got netgear ME102 AP and MA401 pc card.
[15:13] <ghostgum> Bought yesterday.
[15:14] <ghostgum> Of course the problem might be Windows XP Home on the notebook computer :-)
[15:15] <maskros> is there a transcript of things said on this channel?
[15:15] <raph> i don't _think_ so
[15:15] <ghostgum> ghost bot keeps it I think, but it's not generally available.
[15:15] <raph> rillian may have logging in his bot enabled
[15:15] <ghostgum> I (and possibly others) log the channel onto our own hard disk.
[15:16] <maskros> some of these discussions should be put on the web somewhere (wiki?)
[15:16] <ghostgum> since most conversation happens when I'm not at the computer (wrong time zone).
[15:16] <raph> maskros: irc logs are far from the best format
[15:16] <raph> they simply need to be written up well
[15:17] <maskros> ok. is there a command /script on, like on inform games?
[15:18] <maskros> what timezones are people here in?
[15:18] <raph> pst here
[15:18] <ghostgum> AEDT = UTC+1100.
[15:18] <raph> rillian is on london time, igorm on st petersburg
[15:19] <maskros> quite a spread, then :) (CET myself)
[15:20] <ghostgum> UTC+0100?
[15:20] <raph> the sun never sets on ghostscript :)
[15:20] <ghostgum> Don't ghosts come out at night :)
[15:20] <maskros> UTC+0100 right
[15:21] <maskros> jumping back to a previous topic... the pdf-objects vs c-structs.
[15:22] * raph 's brain whiplashes
[15:22] <maskros> (did we leave any threads loose?)
[15:23] <maskros> anyway... in mupdf i went with pdf-objects.
[15:23] <raph> not _really_
[15:23] <maskros> we could probably talk forever...
[15:23] <raph> it's still an open design question imho
[15:23] <raph> and if we do go the generic pdf objs route, there are a few other questions
[15:24] <raph> such as how large the scope of the atom pool should be
[15:24] <raph> whether we should allow clients to manage atoms themselves
[15:24] <maskros> i'm not really happy with pdf-objects. the C code using them is very verbose and error-prone. it feels messy.
[15:24] <maskros> mind, it felt like the right decision at the time.
[15:24] <raph> yeah
[15:25] <raph> i think we're on the same page here
[15:25] <maskros> but i'm swinging around. having the structures well defined in C has many benefits.
[15:26] <raph> i think it basically boils down to what language you're working in
[15:26] <maskros> still, it's not a black-and-white decision. the api could send the pdf-objects and fitz would unparse them into internal structs.
[15:26] <raph> in postscript, pdf, and python, pdf objs are easier
[15:26] <raph> in c, c objects are "tighter"
[15:26] <raph> this is true
[15:26] * maskros likes tight. 'e's a minimalist ;)
[15:26] <raph> agreed
[15:27] <maskros> plus the speed benefits of C are lost if we need to pretty much implement a dynamic sub-language for these data types.
[15:27] <raph> anyway, i don't think we need to settle this right now
[15:27] <raph> we'll just push it on the design-decision queue
[15:28] <maskros> true. still, it's a very important decision when designing the api mechanics.
[15:28] <raph> yeah, img->bits_per_component is _much_ more fun in C than if ((status = read_int_param (img_dict, intern_atom(ctx, "BitsPerComponent)) { ... }
[15:29] <maskros> one possibility is of course to abandon C for all but the actual pixel crunching.
[15:29] <raph> heh, yes
[15:29] <raph> i like c for fitz
[15:30] <raph> for most fitz _clients_ there are probably better choices
[15:30] <maskros> but then we lose most of the potential users/clients by virtue of not using C.
[15:30] <raph> ?
[15:31] <maskros> nobody'll use a library coded in some obscure language like SML or Python :)
[15:31] <raph> yes
[15:31] <maskros> much less frobscottle...
[15:31] <raph> indeed
[15:32] <maskros> likewise, using something other than libc and errno-style error and memory mgmt will alienate
[15:34] <raph> it's a delicate balance
[15:34] <maskros> yes. very frustrating... everybody hates the situation, but nobody sees a way out of it.
[15:34] <raph> i have some ideas :)
[15:35] <maskros> shoot.
[15:35] <raph> ok, but i'll need to get back to "real work" soon
[15:35] <maskros> sorry 'bout stealing your precious hours.
[15:36] <raph> no problem, i really enjoy talking with you
[15:36] <raph> the fundamental idea is to have "runtime" annotations to programs, particularly types
[15:36] <raph> so you have a type 'sequence'
[15:36] <ray> Tor and Raph: I really enjoy "eavesdropping" on the discussions as well
[15:36] <raph> actually, 'sequence of T' so it's parameterized
[15:36] <raph> (like SML and/or C++)
[15:37] * ray has more than a passing interest in Fitz working well
[15:37] <raph> no matter what the runtime looks like, you write a[i]
[15:37] <raph> but the generated code varies, potentially a lot, depending on the runtime annotations
[15:37] <raph> if it's C-style, then a[i]
[15:38] <raph> if it's Python, then PySequenceGet (a, i); with appropriate exc handling and unref of the result
[15:38] <raph> and so on
[15:39] <maskros> this would be for specifying inter-language apis, right?
[15:39] <raph> for apis, yes (like swig)
[15:39] <raph> but also implementation
[15:39] <raph> you write your library _in_ this language (unlike swig)
[15:39] <raph> then when you compile it, you bind it to a particular runtime
[15:40] <raph> on java/clr, everything is garbage collected
[15:40] <raph> because doing refcnts in a gc'd runtime is stupid
[15:40] <maskros> ok. a super-language that compiles to both static machine-based code and the dynamic-typing-runtime of choice.
[15:41] <raph> the term 'super-language' isn't quite right, but yes
[15:41] <maskros> :)
[15:41] <raph> it's better to say that it has runtime agility
[15:41] <maskros> a language that compiles to many 'platforms' on the same platform.
[15:41] <raph> most of the time, language designers figure they get full control of the runtime
[15:42] <raph> another major feature, of course, is the presence of dynamic types
[15:42] <raph> so you get to type variables with type 'object'
[15:43] <raph> in a C runtime, it'll do the boxing and dispatch
[15:43] <raph> just like the Py implementation does
[15:43] <raph> but in different runtimes, that'll be whatever 'object' type the host defines
[15:43] <maskros> isnt this sort of what .net is trying to do?
[15:44] <raph> so that, for example, if you define 'sequence of objects', you can stick host objects in it
[15:44] <raph> the goals overlap a bit with .net (clr), but it is significantly different
[15:44] <maskros> so the sequence-object could be implemented in one language, and contain C ints?
[15:44] <raph> clr is the "one true runtime to bind them"
[15:44] <raph> in the same sense that java is the one true langauge
[15:45] <raph> clr is actually not that good at running programs written in other languages
[15:45] <maskros> unfortunate that runtimes and languages have very different semantics for different languages.
[15:45] <maskros> consider mixing java and scheme :/
[15:46] <raph> yes
[15:46] <maskros> i've read some about clr's deficiencies... aren't there plenty of functional programming languages implemented for it?
[15:46] <raph> so in one sense this is an easier problem
[15:46] <maskros> haskell, f#, etc...
[15:46] <raph> well, those are easy :)
[15:47] <maskros> ok....
[15:47] <raph> it's an easier problem in the sense that code written in 'gimel' is designed to be runtime-agile
[15:47] <raph> the roles of client and library are much better defined than in, say, clr
[15:48] <raph> so, for example, you don't get to call-cc
[15:48] <maskros> why 'gimel'? true... a no-frills language will be needed.
[15:48] <maskros> but for libraries, no-frills will do just fine :)
[15:48] <raph> i decided a long time ago that languages have a much better chance of being popular when they contain the third letter of the alphabet
[15:49] <raph> yah, you look at the hoops that libraries go through to be runtime-agile
[15:49] <raph> in C
[15:50] <raph> (another area that's really interestig is implementation of CSP-like primitives)
[15:50] <raph> (that can be done in explicit state-machine style in C, or using threads, etc.)
[15:50] <maskros> yah. decent concurrency, not the mutex+semaphore+shared-memory mess.
[15:51] <raph> exactly
[15:51] <raph> so gimel could be interesting simply because it's a decent implementation of csp
[15:51] <maskros> of course, there is also the possiblity of making everything a server and talking pipes/sockets
[15:51] <raph> the only other half-decent csp implementation i've seen is limbo, and that has its own problems
[15:52] <maskros> (not well-read about csp) erlang has some nice concurrency primitives.
[15:52] <raph> i've heard that; haven't looked carefully
[15:52] <raph> i vaguely recall that they're inspired by csp as well
[15:52] <raph> hoare's book is quite fun; i recommend it
[15:53] <raph> unfortunately, my copy seems to have gone astray
[15:53] <maskros> basically, erlang is a stripped functional/prolog mix with dynamic types, pattern matching and concurrency. spawn/3 to fork a new 'process' and <pid-exp> ! <msg-to-send>
[15:54] <raph> that sounds csp'ish
[15:54] <maskros> right. yet another book to add to my shopping-list... there are so many things i've been meaning to get around to...
[15:54] <raph> you're young yet :)
[15:55] <maskros> erlang processes are very light-weight (a few hundred bytes, according to Joe Armstrong (inventor of erlang) who approached me about AeKit just the other day)
[15:55] <maskros> nice excuse :)
[15:56] <raph> same is true of limbo
[15:57] <raph> limbo 'threads' turn into os threads when they do blocking i/o calls
[15:57] <maskros> sounds nice. is limbo worth looking at?
[15:57] <raph> however, the limbo implementation has a global interpreter lock, just like python
[15:57] <raph> i'd say so, yes
[15:58] <maskros> ok. erlang does its own scheduling, not sure how it does i/o. it's been over a year i checked it out.
[15:58] <raph> for something that's trying to do concurrency, i'd consider lack of smp ability to be a lose
[15:59] <raph> of course, it's important to separate language deficiencies from implementation deficiencies
[15:59] <maskros> well, the ! can send messages to processes over the net :)
[15:59] <raph> yeah; of course in practice there are all kinds of real problems with that
[16:00] <raph> it's ok if you're implementing multiprocessor parallelism with a cluster,
[16:00] <raph> not ok at all if you're trying to use it as an abstraction layer in designing network protocols
[16:01] <raph> a lot of the misuse of corba can be ascribed to the latter
[16:01] <maskros> of course. but non-shared memory and not requiring locks and synchronization seems a plus
[16:01] <raph> yes, without doubt
[16:01] <maskros> agreed. network protocols should be network protocols, not just what the runtime happens to marshal.
[16:02] <maskros> so, this 'gimel', do you have anything written down about it, or is it all in your head?
[16:03] <raph> mostly in my head, with a teeny prototype
[16:03] <maskros> and i still don't get the connection between the letter between b and d being popular and its name...
[16:04] <raph> well, why do _you_ think Microsoft chose "C" as a prefix for their language name?
[16:04] <raph> they suffix with punctuation, i switch to a different alphabet
[16:05] <maskros> d'oh. i'm dense today :)
[16:05] <raph> i have decided that the best thing to do with these ideas is write them up
[16:05] <raph> but right now, my writing-up queue is basically dominated by my phd thesis
[16:05] <raph> btw, do you have a non-handwavy reference for enfilades?
[16:06] <maskros> yes. let me rack my brain for it.
[16:06] <maskros> there was a wiki.
[16:06] <raph> i see http://xanadu.com/tech/ but am a bit put off by all the bragging about how secret it used to be
[16:06] <maskros> they opensourced their old code.
[16:07] <raph> i know
[16:07] <maskros> would you mind sharing the stuff you wrote about gimel?
[16:07] <maskros> http://www.sunless-sea.net/wiki/EnfiladeTheory
[16:07] <raph> thanks
[16:07] <raph> i don't mind, no
[16:08] <maskros> good. if you want, and have time, would you mind having a look at frobscottle?
[16:08] <raph> sure
[16:08] <raph> i'd love to, but please not this week :)
[16:08] <maskros> busy week, eh?
[16:09] *** adcoby has joined #ghostscript
[16:09] <raph> yeah; i'm trying to catch up on my urgent to-do's
[16:10] <maskros> ok. i'll try to stay out of your hair :)
[16:10] <raph> http://casper.ghostscript.com/~raph/gimel.tar.gz
[16:12] <raph> what you see there is basically only a python runtime
[16:13] <ray> Hi, dan
[16:13] <adcoby> hi ray
[16:13] <raph> dan: how goes?
[16:13] <ray> So, how is IRC working for you now ?
[16:14] <raph> it's similar to pyrex in that regard
[16:14] <adcoby> Everything is going well.  I am back to looking at Jan's last set of changes.
[16:14] <raph> ok
[16:15] <adcoby> ray:  I have not done anything about the time out problem.  Going to winproxy would mean setting up the network again which is annoying.
[16:16] <adcoby> I would rather find out which things IRC needs and punch a few holes in the firewall for them.
[16:17] <maskros> ok. no fleshed out language there, but i like the idea of generating code for multiple runtimes.
[16:18] <ray> raph and dan: I assume that you folks heard that we signed a PS+PCL embedded 
[16:18] <raph> yes!
[16:18] <raph> that'll be fun, hopefully in the good sense
[16:18] <maskros> i'm going to have to think about this some more, see if maybe i can do this with frobscottle (which is very strictly typed)
[16:19] <adcoby> yes.  I also saw my name as pat of the effort - which if fine with me.  Is this a diskless system and if so them what sort of disk emulation do we have?
[16:21] <raph> this enfilade stuff is useful for talking about fitz, i think
[16:21] <raph> inherit-from-parent graphics state is 'disp'
[16:21] <raph> and bounding boxes are 'wid'
[16:22] <maskros> exactly!
[16:22] <raph> most rendering (for example, to rgba buffers) can be seen as 'wid'
[16:22] <maskros> i first read about enfilades just after we discussed fitz this summer.
[16:22] <raph> but in the pdf data model, non-isolated groups with non-Normal blend modes break that
[16:23] <raph> so there is really a design choice here:
[16:23] <raph> either rendering in general is not 'wid'
[16:23] <raph> or in that non-isolated case, you have the backdrop as a left child and the group itself as a right child
[16:24] <raph> ie, pdf has [ A group( [ B C ] ) ]
[16:24] <raph> but the actual tree repr is group( [A], [B C])
[16:25] <maskros> the question is how the transformation can be done mechanically
[16:26] <maskros> what if two non-isolated groups overlap?
[16:27] <raph> it's analogous to the linear-state-change to tree rewrite
[16:27] <maskros> then it shouldnt pose a problem? (i dont know enough about PDF 1.4 transparency to tell)
[16:27] <raph> 'op1 ... op2 set-foo op3 ... op4' becomes:
[16:27] <raph> [ op1 ... op2 set_foo ( op3 ... op4 ) ]
[16:28] <raph> here, the sequel becomes a child
[16:28] <raph> for these NI groups, it's the prequel that becomes a child
[16:28] <raph> so the transformation isn't _difficult_
[16:28] <maskros> right.
[16:28] <raph> it's just not clear to me what's the right thing to do
[16:29] <maskros> it's just a big messy transform, swallowing an entire tree.
[16:29] <raph> which is more important, harmony with the pdf data model, or the conceptual elegance of wid-ness?
[16:29] <maskros> i prefer the conceptual elegance.
[16:29] <maskros> but that could be because i want to use fitz outside of the pdf world
[16:30] <raph> yes
[16:30] <raph> well, if you're not actually doing non-Isolated non-Normal Groups, then you shouldn't have to worry about it
[16:31] <maskros> and with the enfilade model, the tree with all changes can have revision history making undo a very easy thing to do
[16:31] <raph> and I think there's a strong case to be made for only worrying about those coming from PDF files
[16:31] <maskros> how common do you expect NI NN groups to be?
[16:31] <raph> the question is not whether the fitz tree is an enfilade (it is), but rather whether rendering has the wid-ness property
[16:32] <maskros> true. would wid-ness be good for caching?
[16:32] <raph> in other words, do we want to enrol the fitz design in the wid-ness protection program?
[16:32] <maskros> :)
[16:33] <raph> yes, wid-ness is key for caching
[16:33] <raph> urgh... the 'key' pun was unintentional
[16:33] <raph> i expect these NI NN groups to be quite rare
[16:34] <raph> in any case, i think caching still works, it's just that you need more intelligence about it
[16:34] <maskros> less intelligence needed is better.
[16:34] <raph> and i think most of that intelligence can be node-local
[16:35] <raph> i.e. when you traverse an NI NN Group node, you know that you can't cache the rendering of the child
[16:35] <raph> ah, i think i see better now
[16:35] <maskros> but having to account for NINN groups everywhere?
[16:35] <maskros> ok...
[16:36] <raph> if you went the pure-enfilade route, you would be able to cache, and an invalidation of your left child (the backdrop) would invalidate the rendering at the group level
[16:36] <raph> if you want to do caching in the pdf model, you have two choices:
[16:37] <raph> 1. don't cache renderings for NI NN Groups
[16:37] <raph> 2. do caching, but allow propagation of change notification in other directions than up
[16:37] <raph> the latter is most definitely unappealing.
[16:38] <maskros> mhmm
[16:38] <raph> getting change notification right will be hard enough as it is
[16:38] <raph> however, i find (1) completely acceptable
[16:38] <maskros> yes
[16:39] <raph> it's an interesting question, though
[16:39] <raph> by nailing down the data model now, we preclude the optimization later, except at great pain
[16:39] <raph> and in general, i'm trying to design things to make future optimizations possible
[16:40] <raph> this, i think, will be the exception that proves the rule
[16:40] * maskros doesn't quite follow. he's tired.
[16:41] <raph> it's not trivial
[16:42] <raph> pdf 1.4 transparency is quite complex; i think they tried on purpose to make it difficult for competitors to understand
[16:43] <raph> took me a couple of months to wrap my head around it
[16:43] <maskros> somehow i can understand why pdf/x & co was invented
[16:44] <maskros> will anybody use the transparency, or will it just lie unused like PEX?
[16:45] <raph> yes, it's used
[16:45] <maskros> damn!
[16:45] <raph> 95% of users will probably just use the alpha bits though
[16:45] <raph> on mac osx, that's pretty much the story
[16:46] <maskros> yup. that's all that quartz exposes.
[16:54] <raph> right
[17:01] <maskros> ok, that's between 21-02 and 07-09 local time.
[17:02] <maskros> i should go to bed now. g'night.
[17:02] <raph> night
[17:02] *** maskros has quit IRC ("zzz")