On Thu, Aug 26, 2010 at 11:11 AM, Aaron Plattner <[email protected]> wrote: > On Thu, Aug 26, 2010 at 05:43:53AM -0700, Pat Kane wrote: >> BTW, while trying to grep my dead trees I noticed that the current X server >> contains some HAKMEM code, in ./mi/micmap.c I see this hack: >> ... >> count = (visuals >> 1) & 033333333333; >> count = visuals - count - ((count >> 1) & 033333333333); >> count = (((count + (count >> 3)) & 030707070707) % 077); /* HAKMEM 169 >> */ >> ... > > Hah, awesome. > > Apparently that code sucked in 1995 and still sucks today: > http://compilers.iecc.com/comparch/article/95-07-080 > > I increased the loop count by two orders of magnitude: > > NAIVE: 5.616 sec > HAKMEM: 7.541 sec > HAKMEM_P: 8.381 sec
There are lots of interesting articles on this subject, one of which is http://www.dalkescientific.com/writings/diary/archive/2008/07/03/hakmem_and_other_popcounts.html There was also a thread on mesa-dev called "minor u_math.h speedup fun" on 11/28/09 that's worth reading. Matt _______________________________________________ [email protected]: X.Org development Archives: http://lists.x.org/archives/xorg-devel Info: http://lists.x.org/mailman/listinfo/xorg-devel
