David Kastrup <[email protected]> writes: > I don't think that anything close to a sensible implementation can be > significantly simpler or significantly more efficient. There are some > things that may be nicer to do in C, and some shortcuts that may be > taken. But as a functional sketch, this should more or less be what it > takes. > > I don't think we can get this much cheaper.
> ;; Structure of source: a list exactly as long as the list reaching > ;; from cache inclusively to tail exclusively, and associated 1:1 with > ;; the respective list elements. Each element of source has the > ;; following parts: > ;; car -> records whether this property was entered with \once or > ;; not. > ;; cdr -> length of nested property path. After this many cdar > ;; calls on the property alist, you reach the set value of > ;; the nested property. All other content of the property > ;; alist entry is taken from other alist entries. Well David, I should not want to let you implement this in the current form without any feedback from the developer list. When you try converting your approach into C code, you'll likely notice a few problems where performance might be suboptimal. The one thing to note is that fold-right is an inefficient function to use, and because of the guile implementation, greatly more so if you use it with more than a single list. It is still O(n), but with a factor of ugliness that warrants some polishing up, the simplest polish-up possibly just consisting in hard-coding the case for 2 lists instead of using general code. But that still results in complex code and a recursion filling up the stack before actually starting any work working the stack down to empty again. So let us see what you are using fold-right for. Its main purpose appears to be for updating a context's personal part of the property list in reverse, back to front. And it is only in this context that you are actually using "source". So basically, there seems to be little incentive not to keep source in reversed form in the first place. The second point of interest is seeing what you are using source for. One thing "source" is used for is keeping score of "once". We need that in order to clear all "\once\override" commands at the end of a time step. And we need it in order to check whether a "[\once]\revert" applies to some property or not. But if you make this list sparse (as in storing only the elements with once being #t), it should work just fine. How to find out you are processing a given list element of the alist? Well, we are consing the top level alist entries ourselves, so their identity is established by eq if we don't change the entries. You need to check, however, whether keeping the eq-identity of an entry is feasible when it partly consists of copied sibling properties from somewhere else, and those need to be adapted because of new override/reverts. The other thing "source" keeps track of is the depth of nesting of each override. Making this sparse might not help all that much with regard to efficiency: when we need to consult it, we already are in the process of consing up a new spine, so we are already O(n). The question is how to keep a balance between making the code reasonably efficient as well as understandable, and thus, maintainable. While probably not all too many people are comfortable with that code area in the current state, dealing with nested properties is going to make the situation worse, and that should be kept in check as well as possible. Perhaps you'd want some more opinions. -- David Kastrup _______________________________________________ lilypond-devel mailing list [email protected] https://lists.gnu.org/mailman/listinfo/lilypond-devel
