Improve waymarking algorithm

[ggreif]

Bugzilla Link	6809
Version	trunk
OS	All
Depends On	llvm/llvm-bugzilla-archive#8125
CC	@lattner,@jayfoad

Extended Description

http://llvm.org/docs/ProgrammersManual.html#UserLayout describes the waymarking algorithm as presently used. I propose two enhancements to this scheme, both aimed at higher speed of the Use::getUser() method.

1. When looking at the serial protocol, we see that each binary number starts with a 1 binary digit. While visually appealing, it is clearly redundant. This will reduce each call to getUser() by one iteration in the general case.

2. On 64-bit architectures we can allocate 3 bits for waymarking purposes. This allows 8 bit patterns, and we could come up with clever encodings that give us statistically optimal results for the n < N (with some reasonable fixed N) operand counts. A naive one could be:
   s
   S1 (next one is the User)
   S2 (two farter is the User)
   S3 (three farter is the User)
   00
   01
   10
   11

It would be interesting to study the probability densities of use_iterators, (i.e. histograms of getUser() iterations).

This algorithm could be similarly QuickChecked in a reference implementation and transcribed into C++.

Template metaprogramming could select the right algorithm for the host architecture at LLVM compilation time. We have a wide variety of buildbots that would validate the implementation for both 32 and 64 bits.

3. This is applicable tweak for both ideas above: Pre-compute waymarks for (say) 16 Uses and memcpy() it on initialization, instead of computing waymarks for each case as currently done.

[ggreif]

assigned to @ggreif

[ggreif]

I think I could do this :-)

[ggreif]

I think I could do this :-)

Okay, I have a new reference implementation
of the waymarking (en/decode) algorithm:

https://svn.berlios.de/viewvc/al4nin/trunk/purgatory/GetUser.lhs?revision=815&view=markup

Intuitively it replaces every "s1" substring of the
output with "s", akin to the sed parlance:
s/s1/s/g
in this description:
http://llvm.org/docs/ProgrammersManual.html#UserLayout
(This is not exactly correct, as the digits also change)

It saves one iteration, which can be substantial for n < 64 Uses.
Additionally, the density of stop-bits ('s') increases, which
means we waste less iterations for searching the next stop-bit
when we happen to see a digit.

[lattner]

What's the plan for this bug?

[ggreif]

What's the plan for this bug?

Unit tests and improved implementations are on the specified branch given above. Needs to be rebased to current HEAD, though.

What I definitely want to do is to thoroughly Shark out the performance side. I hope to have a Snow Leo MacBook soon, so I can try this with Xcode 4.

Second, as we do many bit level checks, I want to look at the assembly output (esp. clang's on x86). For checking the lowest 2 (resp. 3) bits I expect to see something like:

move ptr, rA
rorc 2, rA ; rotate right into carry and sign
jumpc @​carrysetX1
jumpneg @​handlecase10
@​handlecase00:
...
done
@​handlecase10:
...
done
@​carrysetX1:
jumpneg @​handlecase11
@​handlecase01:
...
done
@​handlecase11:

...
done

I guess LLVM DAGCombine does not know this trick yet. (I used it on MC680xx)

Otherwise the branch is functional.

[ggreif]

What's the plan for this bug?

...

I guess LLVM DAGCombine does not know this trick yet. (I used it on MC680xx)

this is what I mean:

http://docs.sun.com/app/docs/doc/802-1948/6i5uqa9p5?l=en&a=view

It allows to remove a bunch of masking/compares that is present now (in gcc output).

Otherwise the branch is functional.

[ggreif]

Reference impl. is (evolving) here:
https://svn.berlios.de/viewvc/al4nin/trunk/purgatory/GetUser.lhs?view=markup

C++ implementation is done here:
https://llvm.org/svn/llvm-project/llvm/branches/ggreif/waymark-64/
but needs rebasing for llvm-2.8 and trunk.

NB. all "farter"s above should be "farther" :-)

But seriously here is another tweak that just occurred to me:

We could change the specification to detect "hung-off" use arrays better (faster) by using a special stop-stop combination in 3-bit mode:
Instead of ending with "s1x0syxS" we could end with "s1?0sy?X" in the hung-off case, but we would need to sacrifice the "x" stop. Is it worth it?

[ggreif]

The algorithm is pretty sensitive to the way how the

switch(ptr & 3) { case 0: ...; case 1: ...; ... }

construct is lowered by the LLVM optimizers.

[ggreif]

Okay, more than a year passed and I am back with an awesome idea. Maybe because I am feverish, but I think I cracked it and we can have constant-time (small constant factor) getUser() from the last 4 (last 8 on 64-bit systems) Uses in the array. The logarithmic case should also improve a bit.

Here is the idea:

s = 0 (small stop)
S = 1 (full stop)
0 = 2 ('zero' bit)
1 = 3 ('one' bit)

This is almost like before. But the last 4 elements of the array are filled thus:

-------------------------+
...#0|2|2|0|3|2|1|
-------------------------+

Translated:
-------------------------+
...|s|0|0|s|1|0|S|
-------------------------+

The very first access is speculative:

uintptr_t speculativeOffset(this->Prev & 3);
if (!speculativeOffset)
{
if (this[3].Prev & 3 == 1) {
{
// array end is (this + 4)
// continue old algorithm
}
else
{
// we are on a small stop, process from there
}
}
else if (this[speculativeOffset - 1].Prev & 3 == 1) {
// array end is (this + speculativeOffset)
// continue old algorithm
}

It is plain to see that we can never access elements past end.

Here is the new small-stop processing code:

uintptr_t firstBit((this[1].Prev & 1) << 1);
uintptr_t secondBit(this[2].Prev & 1);
uintptr_t offset(4 | firstBit); // we know that the MSB is always 1
uintptr_t code(this[3].Prev & 3);
offset |= secondBit
// continue with code processing as usual
// note, we cannot have full stop here

---

The 64-bit algorithm is even better:

s = 0 (small stop)
S = 1 (full stop)
0 = 2 ('zero' bit & stop)
1 = 3 ('one' bit & stop)
00 = 4 (double 'zero')
01 = 5 ('zero' then 'one')
10 = 6 ('one' then 'zero')
11 = 7 ('one' then 'one')

--------------------------------+
... #0|4|2|0|7|6|5|4|3|2|1|
--------------------------------+

Translates to:

-----------------------------------+
... |s|00|0|s|11|10|01|00|1|0|S|
-----------------------------------+

The overall algorithm is the same, but decoding in small-stop processing differs a bit:
uintptr_t firstTwoBits(this[1].Prev & 3);
uintptr_t code(this[2].Prev & 3);
uintptr_t offset(4 | firstTwoBits); // we know that the MSB is always 1
if (code >= 4)
{
// bump another two bits
}
else
{
// process some form of stop
// note, we cannot have full stop here
}

############## Summary ##############

I expect a significantly faster getUser() for the (very common) last 4 Uses (8 for the 64-bit archs), so we can get back some speed that we lost with use-diet originally (about 1,8% IIRC).

how to proceed

I'll write a reference implementation in Haskell soon, and QuickCheck it, then I'll get to the C++ implementation. I already have a branch that does some unit tests with the old scheme, I'll dig that up, too.

Then when all this works I'll improve the setting up of waymarks with a compact precomputed scheme. That should bring some extra boost.

Finally I'll get to the docs.

[ggreif]

I have a complete (tested) implementation on a restarted (from early 3.5 trunk) branch:

https://llvm.org/viewvc/llvm-project/llvm/branches/ggreif/waymark-64-new/?sortby=log#dirlist

It has automatic algorithm selection for 32/64 bit pointers, and should (more than) halve the memory accesses for decoding getUser.

I'll present the new algorithm at EuroLLVM 2014 with a lightning talk.

[ggreif]

mentioned in issue llvm/llvm-bugzilla-archive#8125

[ekatz]

Implemented in the commit 154d517.
Though the Waymarking has been removed from Use by the commit ff9379f because it improves performances.