Re: Speed difference in Gnus
I'll be looking more carefully at this later, but a couple of quick
corrections and clarifications.
I see your point about priorities, it's especially clearer when you
put it in terms of redisplay access vs. extent modifications as the
typical cases.
>>>> "Ben" == Ben Wing <ben(a)xemacs.org>
writes:
Ben> yes, i do. once i get the new text property implementation down, then
Ben> any program that only uses text properties and not directly uses
Ben> extents or overlays, or which only uses extents/overlays covering
Ben> small sections of the buffer, will be fast.
That's useful to know; I wasn't sure.
> Something like this? A linked list P of (buffer position, extent
This was originally an array, which is where the "finding n is O(lg
n)" came from.
> list) pairs, with an intervals defined as [P[n].pos,P[n+1].pos)
for
> each n. An extent is a pair of pointers into P defining which
> fragments are covered by the extent plus a property list. P[n].ext is
> the list of extents covering that interval. Then for random access,
> finding n is O(lg n), and finding the property is O(|P[n].ext|), which
"Finding n" == "finding the n such that P[n].pos = some_position".
> is the best you can get, I guess. (For many operations, in
particular
> redisplay, which walk P in order, finding n is O(1), right?) P itself
> only needs to be updated when text is inserted/deleted in the buffer,
> and when an extent is created/deleted. |P| <= |# boundary points of
> all extents|, so that is no worse than what we currently have, and we
> never have to update the extents themselves.
Ben> what do you mean "we never have to update the extents
Ben> themselves"?
Since the extents are pointers to *links*, and
links will be inserted/deleted only when fragments are split/coalesced,
which occurs only when an extent is "created with an endpoint not in
the list"/deleted,
the pointers in the extents never need to be updated.
You make the same point. What I missed is:
Ben> the array, btw, is necessary so that we can locate the
Ben> interval surrounding a particular position in O(lg n) time. it's not
Ben> possible to do this in a pure linked list; you'd get O(n) instead.
Ben> [1] how are unicode fonts handled under X windows?
Not, as far as I can tell.
Ben> [2] now that i look more at ccl, i see that it's utterly tied
Ben> to the old mule encoding, as it expects to look directly at
Ben> the internal encoding of the text. it would have to be
Ben> radically restructured for it to work on a
Ben> character-by-character level, not byte-by-byte. do you think
Ben> it's reasonable to just make ccl be an optional feature that
Ben> is compiled in only with old mule?
Yes. I think that CCL has four interesting applications that I know
of: shift-jis, big5, mule-ucs, and fast table-based character sets
(eg, KOI8). The first two have been in C forever, and the latter two
are in C in the unicode support now (at least in principle).
There are also some minor hacks from Aidan and others.
It might be worth using the CCL interpreter as a general fast
arithmetic engine for small numbers, but rip out the Mule stuff.
--
School of Systems and Information Engineering http://turnbull.sk.tsukuba.ac.jp
University of Tsukuba Tennodai 1-1-1 Tsukuba 305-8573 JAPAN
Ask not how you can "do" free software business;
ask what your business can "do for" free software.