www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 4717] New: std.bitmanip.BitArray changes

reply d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4717

           Summary: std.bitmanip.BitArray changes
           Product: D
           Version: D2
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: enhancement
          Priority: P2
         Component: Phobos
        AssignedTo: nobody puremagic.com
        ReportedBy: bearophile_hugs eml.cc



The method sort() of std.bitmanip.BitArray doesn't look so useful, and it may
be removed.

On the other hand there is some very commonly useful functionality that it is
missing in BitArray:
1) b[] = 0; and b[] = 1; to set and reset the whole array quickly, this is a
very common need.
2) countSet(): returns the number of bits set inside the bit array.
3) flip(n): to invert the state of the n-th bit of the bit array.
4) set(n): to set (to 1) the n-th bit of the bit array.
5) reset(n): to reset (set to 0) the n-th bit of the bit array.
6) flipAll(): to invert the state of all bits of the bit array.
7) toSting(): that converts the bit array into a string like
"BitArray(\"0101010011001\")".
8) this() (constructor) method that builds a bit array from a string like
"0101010011001", it's the opposite of the toString().

Optionally:
9) Basic Range interface for the BitArray, so you may use map() on it.
10) firstSet(): returns the index of the first bit that is set, starting the
search from the less significant bit. This is for more specialized usage, like
some heaps.


Notes:
- 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.
- The flip(n), set(n) and reset(n) methods are useful because they may be made
more efficient than opIndexAssign().
- Regarding firstSet(), see also the __builtin_ffs() built-in function of GCC.
- Methods like opXorAssign() probably need to be converted to the new operator
overloading of D2.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Aug 23 2010
next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4717




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: -------
Aug 23 2010
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4717


Don <clugdbug yahoo.com.au> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |clugdbug yahoo.com.au





 - 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: -------
Aug 24 2010
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4717




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: -------
Aug 24 2010
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4717






 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 a&b.
And with 3 words a, b, c, the low bit of the sum is a^b^c and the high word is
(a&b)|((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((a&b)|((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: -------
Aug 24 2010
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4717




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: -------
Aug 24 2010
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4717




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: -------
Aug 24 2010
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4717






 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: -------
Aug 25 2010
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4717




See also bug 4124 and bug 4123

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Aug 26 2010
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4717




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: -------
Sep 22 2010
prev sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4717






 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] = (i&1) + ((i&2)>>1) + ((i&4)>>2) + ((i&8)>>3) +
            ((i&16)>>4) + ((i&32)>>5) + ((i&64)>>6) + ((i&128)>>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: -------
Sep 22 2010