Re: Speed difference in Gnus

Stephen J. Turnbull wrote: yes. yes, i do. once i get the new text property implementation down, then any program that only uses text properties and not directly uses extents or overlays, or which only uses extents/overlays covering small sections of the buffer, will be fast. however, in the long run that's not enough; we'd like for extents to be fast, period, and not make the user go through the text property interface. (the reason why this is harder is that the text property interface is higher-level and doesn't explicitly give you a concept of an entity tied to a particular range.) if people normally used text properties, and tended to only use a small number of extents, then we might consider as a stop-gap measure separating the two internally into a sort of parallel structure -- this is much like what FSF does, with its overlays, i think. however, it might turn out to be not much easier to implement that than to just move entirely to the "correct" implementation of extents in terms of non-overlapping intervals. this sounds about right, although i'm a little confused about what "finding n" means, and finding anything in a linked list is O(n), not O(lg n). we maintain an ordered gap array (or whatever) of non-overlapping intervals as defined by the extents, where each interval is the maximum stretch not crossed by an extent endpoint. Each extent contains a pointer to the first and last interval covered by the extent. most likely, these will be indices into the gap array, and hence need to be adjusted as we do gap movement in the array; this is just like what happens currently with the endpoints of an extent in the buffer. we can avoid this update if the gap array, rather than containing the interval structures themselves, contains pointers to heap-allocated interval objects, and each such object contains a forward and probably backward pointers to the next/previous object, so that essentially the intervals are in a combination linked-list and array. the array, btw, is necessary so that we can locate the interval surrounding a particular position in O(lg n) time. it's not possible to do this in a pure linked list; you'd get O(n) instead. another data structure would involve having the intervals be objects with pointers back to the array position they came from. doing gap movement in the array requires updating the intervals rather than the extents; there could potentially be significant savings if there are a whole lot of overlapping extents but in practice this seems unlikely. in reality i'm somewhat loath to do any of these alternative schemes because it would add a lot of space overhead, would fragment the memory, etc. in practice, i think that extents are modified much less often than they are accessed by redisplay, and you only get O(n) behavior when inserting or deleting extents when the gap is far away from where you previously were. but i'm certainly willing to be proven wrong by appropriate profiling data. the crucial thing, then, is that each interval contains a some sort of list of all the extents overlapping that interval. this list will probably be small; so either a linked list or a Stynarr could be used. (A Stynarr is a new struct that i invented in my unicode-internal ws. it is based on existing face-cachel code. the idea is that it uses a fixed array of small size (e.g. 4 or 6) that's built into the object and pointer to a dynarr, which is used to handle overflow. it's useful when you need to maintain a list of objects and handle an arbitrary # of objects on the list, but where in practice it very rarely exceeds a small # and would like to avoid lots and lots of heap allocation.) we might still have to maintain the display-order and e-order for extent endpoints, like we currently do; i'll have to look into the code, but i bet there will still be places that need to look stuff up by endpoints, and it may not be too easy to derive this from the interval data. what do you mean "we never have to update the extents themselves"? why, because i have limited time and i need to schedule things according to how badly they slow things down. i see that my attempts to speed up byte<->char conversion actually slowed things down significantly for Raymond, although they indeed sped things up in my profiling for whatever i was running into problems with. i think it's because i deleted the "known range" cache that was the first line of attack. i did this because fsf didn't have any such thing and seemed to be doing fine; but they may have a lot more code internally that operates in byte positions rather than char positions [or even in pairs of the two; that seems common]. so i'm going to look into putting them back. meanwhile, i'm mostly done with the rewrite of char tables for unicode-internal. there isn't much coding left before i will start compiling; but there's definitely a good deal of work to be done. for one, the font handling is still by charset, meaning that unicode chars for which there's no charset won't be displayable! yuck. that requires some significant work. for another char-classes haven't been implemented yet. and i don't know what the hell to do with ccl; hopefully it really won't be necessary because i've expanded the notion of charset to include any rectangular subset of 256x256 (so we can properly have a windows-1252 charset, e.g.) and i'm planning on creating a general mbcs coding system to replace the ad-hoc shift-jis and big5 coding systems; it could also be used for windows-125* coding systems plus lots of simple coding systems (e.g. iso-8859-1) that are currently handled using iso2022. questions for you, stephen: [1] how are unicode fonts handled under X windows? [2] now that i look more at ccl, i see that it's utterly tied to the old mule encoding, as it expects to look directly at the internal encoding of the text. it would have to be radically restructured for it to work on a character-by-character level, not byte-by-byte. do you think it's reasonable to just make ccl be an optional feature that is compiled in only with old mule? no, not in the long run.