On Wed, Sep 12, 2012 at 7:35 AM, Adrian Buehlmann <span dir="ltr"><<a href="mailto:adrian@cadifra.com" target="_blank">adrian@cadifra.com</a>></span> wrote:<br><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">

<div>I think this should be considerably simpler to translate into C code<br>
than _auxencode.</div></blockquote><div><br></div><div>I'm not quite opposed to the idea of replacing the current hybrid encoding scheme with something new, especially given bug 3621. But let me outline some thoughts below.</div>
<div><br></div><div>Given my recent experience, I think that probably the best way to determine that an encoding scheme can be both efficient and comprehensible is to implement it in C.</div><div><br></div><div>Perhaps accidentally, the current basic encoding scheme actually fulfils both criteria of efficiency and comprehensibility.</div>
<div><ul><li>It can be implemented with a simple state machine.</li><li>We can identify a path that does <i>not</i> need escaping in a single pass, and in such cases we can allocate no extra memory and do no copying.</li>
<li>Even when a path must be escaped, we can do so with just a single allocation and one more pass.</li>
<li>In the no-escape case, no byte in a path needs to be inspected more than once.</li></ul>(And conveniently enough, the current auxencode can be implemented as a variant of basic encoding by just driving the same function with a couple of different lookup tables. As a result, it costs just a few extra lines to implement. That's a big saving in complexity.)</div>

<div><br></div><div>Compare this to the hashed encoding scheme. It's not immediately easy to see from the Python code, but a major difficulty with the hashed encoder is that it *must* be implemented using multiple passes, extra code paths, and copies, due to the data dependencies and variations over basic encoding.</div>
<div><ol><li>The SHA-1 hash must be computed over the dir-encoded name, which means that we have to dir-encode a path before we do anything else.</li><li>We need a separate code path specially for dir-encoding.</li><li>The lower case encoding scheme is different than the one used for basic encoding, so it too must have a separate implementation.</li>
<li>We then aux-encode the lower-encoded text.</li><li>Once that's done, there's an additional very complicated copy-and-fixup step (named "hashmangle" in my patches). This may truncate and tweak every path component, and it then has to do lots of further surgery to glue together all the parts together with the SHA-1 hash and the original suffix.</li>
</ol><div>We have five passes over the name here: direncode, hash, lowerencode, auxencode, mangle. It's conceivable that we could combine the last three passes into one using a suitably clever state machine, but that looks like a nightmarish prospect to me :-)</div>
<div><br></div>So really, given the above, it shouldn't surprise you that I think that auxencode, considered in isolation, is not the problem at all. (Based on brief inspection, I also don't think that the proposed change would simplify the auxencode state machine by more than a small amount.)</div>
<div><br></div><div>Before I continue, I think that we could fix bug 3621 with just an hour or two of work on both the C and Python sides: just don't append the original suffix (this is where the unbounded length comes from), and call the new scheme fncache2. Boom! Done.</div>
<div><br></div><div>If you want to explore a simpler hashed encoding scheme, here's what I think it should be:</div><div><ol><li>Compute the hash (presumably still SHA-1) of the original pathname.</li><li>Basic-encode the original pathname, using the scheme we already have. Either stop or truncate at 210 bytes.</li>
<li>Truncate each path component and fix up any dangling spaces or dots that arise.</li><li>Append the hash to the end of the result of step 3.</li></ol>This is quite simple. It avoids the need for separately dir-encoding and lower-encoding a path, along with much of the complexity of my hashmangle function. It has better data dependencies, too. Conceptually, it looks like it needs 3 passes over the pathname (hash, encode, truncate), which is already an improvement, but it could be implemented in just 2 if someone really cared (at a cost of another state machine and more code, and probably negligible benefit in performance).</div>
</div>