Hi Robby,<div><br></div><div>I've been looking at a profile of DrRacket when opening/indenting large files. Using the statistical profiler, I've measured a large chunk of time (around 40%) is dedicated to the search operation of the existing syntax-color token-tree. That seems too high, so I've been trying to understand what's going on there.</div>
<div><br></div><div>I suspect that the access pattern that's applied on the tree during indentation resembles the worst-case scenario of splay trees: if we search each node in sequential order, the structure of a splay tree will linearize, ruining the dynamic balance. Indentation uses a repeated, sequential search across the tokens.</div>
<div><br></div><div>Concretely, if I add the following diagnostic to the token-tree% class:</div><div><br></div><div>--------------------------------------------------</div><div><div><div>+ (define (height node)</div><div>
+ (cond</div><div>+ ((not node) 0)</div><div>+ (else</div><div>+ (add1 (max (height (node-left node))</div><div>+ (height (node-right node)))))))</div><div>+</div></div></div><div><div> ;; Moves the node at key-position to the root</div>
<div> (define/public (search! key-position)</div><div> (when root</div><div>- (set! root (internal-search root key-position))))</div><div>+ (set! root (internal-search root key-position))</div>
<div>+ (printf "debug: size: ~a, height: ~a\n" (size root 0) (height root)))</div><div>+</div></div><div><div>--------------------------------------------------</div><div><div></div></div></div><div><br>
</div><div>and open up a large file like collects/drracket/private/unit.rkt, I can see that the tree is much deeper than it deserves to be. During a tabify-all, the tree does appear to get huge; it swings between a height in the hundreds into the thousands thousands. That's much too tall, considering that there are only about 40000 tokens in the tree.</div>
<div><br></div><div><br></div><div>I believe that a balanced BST should give us better performance. I have been writing an alternative implementation of the token tree based on red-black trees.</div><div><br></div><div>
<a href="https://github.com/dyoo/new-token-tree">https://github.com/dyoo/new-token-tree</a></div>
<div><br></div><div>It is unfortunately missing the necessary splitting operations. But I plan to implement split and concat with the algorithm described in:</div><div><br></div><div> <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.109.4875">http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.109.4875</a></div>
<div><br></div><div>so I don't anticipate fundamental problems.</div><div><br></div><div><br></div><div>I wanted to surprise you by getting this all working by mid-week, but it's taking longer than I thought... :) So I might as well run it by you to make sure the idea is sound before I go further on this track.</div>