[LLVMbugs] [Bug 6809] New: Improve waymarking algorithm

[bugzilla-daemon at llvm.org]

http://llvm.org/bugs/show_bug.cgi?id=6809

           Summary: Improve waymarking algorithm
           Product: libraries
           Version: trunk
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: enhancement
          Priority: P
         Component: Core LLVM classes
        AssignedTo: unassignedbugs at nondot.org
        ReportedBy: ggreif at gmail.com
                CC: llvmbugs at cs.uiuc.edu


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.

-- 
Configure bugmail: http://llvm.org/bugs/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.