[Date Prev][Date Next][Thread Prev][Thread Next][Author Index][Date Index][Thread Index]

Last item in Green thread

At 11:33 AM -0700 10/19/00, roger gregory wrote:

"David G. Durand" wrote:

 >Right since Gold is MANY generations of design from Green, there are few
 >direct identities.  Mostly anything that would limit performance to
 >square root
 >is avoided in Gold (note that poom and span have square root worst case).

 You can do span (range) queries in log N + S time (log of number of
 spans, plus the size of the result set). Of course that's a different

Right, we might wnat to replace the spanf with some other algorithm, when
we make it allow for editibility of links, and visibility protections for
protected documents.

 > >>Somewhere, perhaps in the granfilade (using a distinguished range of
 >>addresses?) there's a global map that maps Xanadu server, account,
 >>document, etc. addresses down to a single poomfilade per document.
 >The addresses map directly to the granfilade via the addresses.

 So some granfilade addresses are externally visible ones (V-space
 addresses that MIRV out via the Poomfilades), and some are internal
 I-space addresses.

Well they are all I-addresses, but the document addresses are visiable.

 > I came to look at addressing as much more critical later on, and it's
 > the key to my dissertation work, but by then I was more interested in
 arbitrary combinations of changes and undo, coupled with the ability
 to make edit-stable pointers into an alternative version space.

 I devoted a lot less time to algorithms, because it's less important now.

Nope, remember user expectations are higher and the universe is larger.
We knew all of that in advance.  Algorithms, especially those needed for
versioning and the related ability to not ever have to lock documents,
are needed more now than ever before.  In fact our design was too early
to generate user interest.

 >>The problem of fragmenting end-sets is a real one in all of these
 >>schemes, as a linear number of edits can create a linear number of
 >>items that need to be returned in these intermediate queries, which
 >>can make the run-time worse than log in some cases.
 >Well yes but,
>recall that we mostly will want to retireve small pieces of the document, some
 >small multiple of display sizes, and recall that much (often all) of
 >the structure
 >and text will just get cached in ram, the problem is an in CPU problem and
 >not a big "read it in form disk and take forever" kind of thing.

 CPU problems are not problems at all anymore. At least not for most
 data structures. There's a lot of cache-hit questions though around
 disk traffic.

My point mostly, but recall that we don't need all the document at once
and most documents are small  <20Mbytes.   The encyclopedia britanica
12ed seems to be abut 400M, text only!

> >>Here are the random queries I started before coming up with the design above:
 > >>Does the granfilade use tumblers only to allow the creation of new,
 >>linearly ordered insertion points between existing granfilade
 >>addresses? couldn't the granfilade be a linear, append-only
 >>text-space? I guess the granfilade does allow for changes to
 >>non-frozen versions to vanish silently as their versions are edited.

Note that the granfilade is used as linear within a document for the text append.
The tumblers are the the same as the conventional military numbering system
which has time tested uses that match our usage.

>More than that the tumblers allow locality and authorship info to be incoded.
 >Note that Gold hasn't yet decided on a particular address encoding!

 But does the granfilade include server/node/account/info in
 i-addresses? I guess that makes sense, as the bytes are perpetually
 "owned" by the home document.

The addresses are encoded, and perhaps that is a mistake, though it is a small one. Mostly the addresses incode that info to give some locality as documents get moved around
and cached through the net.

 I tend to think of owning the address space that you publish as
 opposed to the bytes at the end, but that reflects my own mental
 drift, not your model. That makes things clearer.

I don't get this, you don't own your text?  How so?

 >>The POOMfilade seems more obscure to me. Does it map from Document
 >>addresses (global Udanax addresses) into the granfilade, or the
 >Poom maps  i<->v
 >spanf maps i<->i
 >so given an i (or granf address) the poom gives a v  (document address)
 >given an ispan the spanf gives the i addresses in the documents
 >(including links) that map
 >to that ispan.

 I guess I still have the poom backwards. How do I go from a v-address
 (e.g. from the front end) to an i-address?

Simple the matrix maps both ways.  The code does also.

 >>Links seem like a natural for the spanfilade, but they seem like they
 >>ought to be stored in document addresses, not granfilade addresses.
 >Ha, that would mean as the document changed the links would point to
 >different stuff.

 yeah, this is a perspective difference. I've spent a decade and a
 half dealing with editing problems, and from that perspective you're
 primarily focusing on a small number of "current states" and
 unwinding the history to determine the original contexts, and do
 document comparisons.

Not to us,  we are focused on a set of notes, and the document built from
them. Thus the parallel text face stuff. Note that there may be many documents that are notes, that are spun together into many different resulatnt documents,
each containing pieces from most/all of the original notes documents.  Some
people habitualy write this way, Tolstoy was famous for it, just as Asimov was
famous for writing high quality first draft at 120wpm and handing it off to his
2 fulltime personal editors.

 >For example showing links as caps for easy ascii representation
 >this is A text with TWO spans linked.
 >   now if the addresses were to the v (document addresses) and we
 >edited by adding 6xes and a space
 >xxxxx thIs is a tEXT with two spans linked.
 >Make more sense now?

 Oh yeah. I actually figured out this mistake before writing my design
 note/query. How do you record the originating document context where
 a link was made? I guess by the link's home address. When you make a
 new rev of a document you also create new links (though structure is
 shared by transclusion). So I guess that tells you what poomfilade to
 use to turn the link spans back into v-spans for a particular

Mostly right.  In the current implementation there is no way to record/find
the originating document context (whatever that means, thus the problem).
This is a bug, but a bug caused by pureism.  A bug nonetheless.

A related bug in both Green and Gold is that they don't have representations
of time, because we couldn't find a way that we could believe that was close to
correct.  Not time zones but special relativity!

 Are you saying that there's no way to find the POOMs pointing to a
 given i-span?

No the spanf finds the pooms that map to the i-span.

 PS. Can I post this thread to the udanax list?

By all means,  and once some one has reviewed the mailing archives, we
can put that up too. I would like to have a tool to allow us to navigate them,
and make sure that we generate/retain a unique id for each mail so we can
refer to them later and still make sense.
David Durand
Chief Technical Officer
Dynamic Diagrams