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

bugzilla-daemon at llvm.org bugzilla-daemon at llvm.org
Fri Apr 9 14:02:47 PDT 2010


           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:
S1 (next one is the User)
S2 (two farter is the User)
S3 (three farter is the User)

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.

More information about the llvm-bugs mailing list