[Issue 4717] std.bitmanip.BitArray changes

[d-bugmail--- via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=4717

--- Comment #12 from github-bugzi...@puremagic.com ---
Commit pushed to stable at https://github.com/dlang/phobos

https://github.com/dlang/phobos/commit/7a3700135944be30279aeaec0aa32849fdc30adc
Fix Issue 4717 - std.bitmanip.BitArray changes

--

[Issue 4717] std.bitmanip.BitArray changes

[d-bugmail--- via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=4717

github-bugzi...@puremagic.com changed:

   What|Removed |Added

 Status|NEW |RESOLVED
 Resolution|--- |FIXED

--

[Issue 4717] std.bitmanip.BitArray changes

[d-bugmail--- via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=4717

--- Comment #11 from github-bugzi...@puremagic.com ---
Commit pushed to master at https://github.com/dlang/phobos

https://github.com/dlang/phobos/commit/7a3700135944be30279aeaec0aa32849fdc30adc
Fix Issue 4717 - std.bitmanip.BitArray changes

--

[Issue 4717] std.bitmanip.BitArray changes

[via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=4717

Andrei Alexandrescu  changed:

   What|Removed |Added

   Keywords||bootcamp
 CC||and...@erdani.com

--

[Issue 4717] std.bitmanip.BitArray changes

[d-bugmail]

http://d.puremagic.com/issues/show_bug.cgi?id=4717



--- Comment #9 from bearophile_h...@eml.cc 2010-09-22 12:24:24 PDT ---
See also:
http://www.strchr.com/crc32_popcnt
http://wm.ite.pl/articles/sse-popcount.html

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
--- You are receiving this mail because: ---

[Issue 4717] std.bitmanip.BitArray changes

[d-bugmail]

http://d.puremagic.com/issues/show_bug.cgi?id=4717



--- Comment #10 from Don clugd...@yahoo.com.au 2010-09-22 13:10:44 PDT ---
(In reply to comment #9)
 See also:
 http://www.strchr.com/crc32_popcnt
 http://wm.ite.pl/articles/sse-popcount.html

Yes, I saw those. 
I made a simple 256-entry table lookup implementation (below, not optimised for
size) which runs at 5 cycles for 4 bytes. It'd be painful to beat that for
general-purpose 32 bit code (because AMD 32bit processors don't support SSE2).
Cache misses will kill you, though, unless the array is quite long.
I include my code here anyway, for future reference.

For 64 bits, SWAR on SSE2 is a clear winner.

--
const(uint[256]) makepopcountlookup(){

uint [256] result;
for (int i = 0; i= 0xFF; ++i)
{
result[i] = (i1) + ((i2)1) + ((i4)2) + ((i8)3) +
((i16)4) + ((i32)5) + ((i64)6) + ((i128)7);
}
return result;
}

__gshared uint[256] POPCOUNT_LOOKUP_TABLE = makepopcountlookup();

/*
 A lookup table is normally a bad way to do popcount since it risks a cache
miss.
 But 1K table is not so terrible, and we're dealing with a large source array.

 The address of the lookup table is passed as a parameter to avoid PIC
problems.
*/
int popcountArray(uint[] src, uint *lookuptable = POPCOUNT_LOOKUP_TABLE[0])
{
enum { LASTPARAM = 4*4 } // 3* pushes + return address.

   // TIMING: Core2: 12uops, 5.0 cycles/uint
   // It's entirely limited by the 5 loads.

asm {
naked;

push ESI;
push EDI;
push EBX;

mov EDI, EAX; // EDI = lookup table.

mov ECX, [ESP + LASTPARAM + 0*4]; // src.length;
mov ESI, [ESP + LASTPARAM + 1*4]; // src.ptr
xor EAX, EAX;

lea ESI, [ESI + 4*ECX]; // ESI = end of src
neg ECX; // count UP to zero.
mov EBX, [ESI + 4*ECX];
xor EDX, EDX;
add ECX, 1;
jz onlyone;
L1:
add EAX, [EDI + EDX * 4];
movzx EDX, BL;

add EAX, [EDI + EDX * 4];
movzx EDX, BH;
shr EBX, 16;

add EAX, [EDI + EDX * 4];
movzx EDX, BH;

add EAX, [EDI + EDX * 4];
movzx EDX, BL;

mov EBX, [ESI + 4*ECX];
add ECX, 1;
jnz L1;

onlyone:
add EAX, [EDI + EDX * 4];
movzx EDX, BL;

add EAX, [EDI + EDX * 4];
movzx EDX, BH;
shr EBX, 16;

add EAX, [EDI + EDX * 4];
movzx EDX, BH;

add EAX, [EDI + EDX * 4];
movzx EDX, BL;

add EAX, [EDI + EDX * 4];

pop EBX;
pop EDI;
pop ESI;
ret 2*4;
}
}

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
--- You are receiving this mail because: ---

[Issue 4717] std.bitmanip.BitArray changes

[d-bugmail]

http://d.puremagic.com/issues/show_bug.cgi?id=4717



--- Comment #8 from bearophile_h...@eml.cc 2010-08-26 07:56:20 PDT ---
See also bug 4124 and bug 4123

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
--- You are receiving this mail because: ---

[Issue 4717] std.bitmanip.BitArray changes

[d-bugmail]

http://d.puremagic.com/issues/show_bug.cgi?id=4717



--- Comment #7 from Don clugd...@yahoo.com.au 2010-08-25 01:47:59 PDT ---
(In reply to comment #5)
 I see, I think you are talking about using a SWAR approach then. I have never
 used it for this job, but it sounds intersting. I'd like to do some benchmarks
 to see what the most efficient solution is among those two.
 It looks like a simple problem, but has a surprisingly high number of
 interesting solutions.

Found the link:

http://www.icis.ntu.edu.sg/scs-ijit/91/91-1.pdf

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
--- You are receiving this mail because: ---

[Issue 4717] std.bitmanip.BitArray changes

[d-bugmail]

http://d.puremagic.com/issues/show_bug.cgi?id=4717


Don clugd...@yahoo.com.au changed:

   What|Removed |Added

 CC||clugd...@yahoo.com.au


--- Comment #2 from Don clugd...@yahoo.com.au 2010-08-24 00:33:44 PDT ---
(In reply to comment #0)
 - The count() is also known known as Population or Hamming weight. This is
 useful for Hamming distances, to count bits in many situations, like for
 example for the Sieve of Eratosthenes. There are ways and refined algorithms 
 to
 speed up this operation a lot. And this is a very commonly useful operation. I
 may offer some D code if you want. See also:
 http://en.wikipedia.org/wiki/Hamming_weight
 http://graphics.stanford.edu/~seander/bithacks.html
 And see also the __builtin_popcount() built-in function of GCC.

Curious fact: the built-in popcount instruction isn't much use for bit arrays.
It's great for 64 bit longs (especially for chess programs!) but once you have
a dozen machine words or more, it's faster to add the bits sideways. An
interesting consequence of this is that Intel/AMD's new popcount instruction is
hardly ever useful...

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
--- You are receiving this mail because: ---

[Issue 4717] std.bitmanip.BitArray changes

[d-bugmail]

http://d.puremagic.com/issues/show_bug.cgi?id=4717



--- Comment #3 from bearophile_h...@eml.cc 2010-08-24 03:57:46 PDT ---
Answer to Comment 2:
The code in the bithacks site I have given URL of probably is what you were
talking about.
But then there are refined algorithms to use the basic code shown in bithacks,
that becomes useful as the bit array gets a little larger.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
--- You are receiving this mail because: ---

[Issue 4717] std.bitmanip.BitArray changes

[d-bugmail]

http://d.puremagic.com/issues/show_bug.cgi?id=4717



--- Comment #4 from Don clugd...@yahoo.com.au 2010-08-24 05:55:05 PDT ---
(In reply to comment #3)
 Answer to Comment 2:
 The code in the bithacks site I have given URL of probably is what you were
 talking about.
 But then there are refined algorithms to use the basic code shown in bithacks,
 that becomes useful as the bit array gets a little larger.

No, that's not what I meant at all. The parallel adding I'm referring to does
not involve any shifts.
You basically implement a half adder. Given 2 words  a, b  the low bit of the
sum is a^b, and the high bit is ab.
And with 3 words a, b, c, the low bit of the sum is a^b^c and the high word is
(ab)|((a^b)c). The popcount is popcount(lo word) + 2* popcount(high word).

So what you do is pass through the array in pairs, grabbing the values a, b.
You accumulate popcount p += 2*popcount((ab)|((a^b)c)). calculate a new carry
c = a^b^c. Then you add p+=popcount(c); at the end. In this way, you've dealt
with two words, but only done one single-word popcount.

In practice, you don't just use pairs, you grab 8 or 16 values at a time, and
keep a 3 or 4 bit sum. You only have to perform one single-word popcount for
every 8 or 16 words. You need to do a lot of logical operations, but they
pipeline quite well.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
--- You are receiving this mail because: ---

[Issue 4717] std.bitmanip.BitArray changes

[d-bugmail]

http://d.puremagic.com/issues/show_bug.cgi?id=4717



--- Comment #5 from bearophile_h...@eml.cc 2010-08-24 06:31:52 PDT ---
I see, I think you are talking about using a SWAR approach then. I have never
used it for this job, but it sounds intersting. I'd like to do some benchmarks
to see what the most efficient solution is among those two.
It looks like a simple problem, but has a surprisingly high number of
interesting solutions.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
--- You are receiving this mail because: ---

[Issue 4717] std.bitmanip.BitArray changes

[d-bugmail]

http://d.puremagic.com/issues/show_bug.cgi?id=4717



--- Comment #6 from bearophile_h...@eml.cc 2010-08-24 14:02:31 PDT ---
For efficiency on 64 bit systems too you may change this code from the BitArray
struct:

struct BitArray
{
size_t len;
uint* ptr;

...

void init(void[] v, size_t numbits)
in
{
assert(numbits = v.length * 8);
assert((v.length  3) == 0);
}



Into:

struct BitArray
{
size_t len;
size_t* ptr; // changed here

...

void init(void[] v, size_t numbits)
in
{
assert(numbits = v.length * 8);
assert(v.length % size_t.sizeof == 0); // changed here
}

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
--- You are receiving this mail because: ---

[Issue 4717] std.bitmanip.BitArray changes

[d-bugmail]

http://d.puremagic.com/issues/show_bug.cgi?id=4717



--- Comment #1 from bearophile_h...@eml.cc 2010-08-23 17:38:53 PDT ---
As alternative flipAll() may be named flip() (with no arguments).

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
--- You are receiving this mail because: ---