Old O'Reilly X books
Matt Turner
mattst88 at gmail.com
Thu Aug 26 12:05:28 PDT 2010
On Thu, Aug 26, 2010 at 11:11 AM, Aaron Plattner <aplattner at nvidia.com> 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
More information about the xorg-devel
mailing list