www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Bitarrays in the age of 64bit

reply Dominikus Dittes Scherkl <dominikus.scherkl continental-corporation.com> writes:
It was said that implementing bitarrays is complicated, because 
of the indexing.

Has anybody ever considered to use bit-pointers?
Nobody really uses the full address range that 64bit pointers 
have - in fact some hardware internally still uses 48bit or 56bit 
address-registers, so instead adding three lower address bits 
would not cost a lot (just forward bit 3..58 to the register 
instead of bit 0..55).
This would also allow for implementing 2bit-types (one that I 
really would appreciate, because it can represent sign values, 
providing -1, 0, 1 and NaN - which is necessary as a comparison 
result for non-ordered values), and 4bit-types (so called 
nibbles).
And with bit-pointers of course implementing arrays of boolean, 
sign, nibbles or even odd-length types would be straight forward. 
All the strange side-effects of byte clustering would vanish.

Just an idea.
Apr 03
next sibling parent reply Jonathan M Davis <newsgroup.d jmdavisprog.com> writes:
On Friday, April 3, 2020 1:31:52 AM MDT Dominikus Dittes Scherkl via 
Digitalmars-d wrote:
 It was said that implementing bitarrays is complicated, because
 of the indexing.

 Has anybody ever considered to use bit-pointers?
 Nobody really uses the full address range that 64bit pointers
 have - in fact some hardware internally still uses 48bit or 56bit
 address-registers, so instead adding three lower address bits
 would not cost a lot (just forward bit 3..58 to the register
 instead of bit 0..55).
 This would also allow for implementing 2bit-types (one that I
 really would appreciate, because it can represent sign values,
 providing -1, 0, 1 and NaN - which is necessary as a comparison
 result for non-ordered values), and 4bit-types (so called
 nibbles).
 And with bit-pointers of course implementing arrays of boolean,
 sign, nibbles or even odd-length types would be straight forward.
 All the strange side-effects of byte clustering would vanish.

 Just an idea.
It has of course been a while since I saw this talk, since I haven't watched it since it was live (so I may be remembering wrong), but it sounds like this talk from dconf 2016 might be applicable: http://dconf.org/2016/talks/sechet.html - Jonathan M Davis
Apr 03
parent reply Faux Amis <faux amis.com> writes:
On 2020-04-04 02:47, Jonathan M Davis wrote:
 On Friday, April 3, 2020 1:31:52 AM MDT Dominikus Dittes Scherkl via
 Digitalmars-d wrote:
 It was said that implementing bitarrays is complicated, because
 of the indexing.

 Has anybody ever considered to use bit-pointers?
 Nobody really uses the full address range that 64bit pointers
 have - in fact some hardware internally still uses 48bit or 56bit
 address-registers, so instead adding three lower address bits
 would not cost a lot (just forward bit 3..58 to the register
 instead of bit 0..55).
 This would also allow for implementing 2bit-types (one that I
 really would appreciate, because it can represent sign values,
 providing -1, 0, 1 and NaN - which is necessary as a comparison
 result for non-ordered values), and 4bit-types (so called
 nibbles).
 And with bit-pointers of course implementing arrays of boolean,
 sign, nibbles or even odd-length types would be straight forward.
 All the strange side-effects of byte clustering would vanish.

 Just an idea.
It has of course been a while since I saw this talk, since I haven't watched it since it was live (so I may be remembering wrong), but it sounds like this talk from dconf 2016 might be applicable: http://dconf.org/2016/talks/sechet.html - Jonathan M Davis
Where did all the dconf 2016 videos go?
Apr 05
next sibling parent Jonathan M Davis <newsgroup.d jmdavisprog.com> writes:
On Sunday, April 5, 2020 4:43:27 AM MDT Faux Amis via Digitalmars-d wrote:
 On 2020-04-04 02:47, Jonathan M Davis wrote:
 On Friday, April 3, 2020 1:31:52 AM MDT Dominikus Dittes Scherkl via
 It has of course been a while since I saw this talk, since I haven't
 watched it since it was live (so I may be remembering wrong), but it
 sounds like this talk from dconf 2016 might be applicable:

 http://dconf.org/2016/talks/sechet.html

 - Jonathan M Davis
Where did all the dconf 2016 videos go?
Well, that's bad. I wonder whose account was used? I'll ping Mike. Maybe he can do something. Hopefully, they're not truly gone. - Jonathan M Davis
Apr 05
prev sibling parent Mike Parker <aldacron gmail.com> writes:
On Sunday, 5 April 2020 at 10:43:27 UTC, Faux Amis wrote:

 
Where did all the dconf 2016 videos go?
The 2016 & 2017 videos were hosted by Sociomantic (now Dunhumby). Unfortunately, someone deleted the account a few days back. We've been in touch with some folks to get the situation resolved. I should know more in the coming days.
Apr 05
prev sibling next sibling parent reply Jacob Carlborg <doob me.com> writes:
On 2020-04-03 09:31, Dominikus Dittes Scherkl wrote:
 It was said that implementing bitarrays is complicated, because of the 
 indexing.
 
 Has anybody ever considered to use bit-pointers?
 Nobody really uses the full address range that 64bit pointers have - in 
 fact some hardware internally still uses 48bit or 56bit 
 address-registers, so instead adding three lower address bits would not 
 cost a lot (just forward bit 3..58 to the register instead of bit 0..55).
 This would also allow for implementing 2bit-types (one that I really 
 would appreciate, because it can represent sign values, providing -1, 0, 
 1 and NaN - which is necessary as a comparison result for non-ordered 
 values), and 4bit-types (so called nibbles).
 And with bit-pointers of course implementing arrays of boolean, sign, 
 nibbles or even odd-length types would be straight forward. All the 
 strange side-effects of byte clustering would vanish.
 
 Just an idea.
Sounds like, or similar, to tagged pointers [1] [1] https://en.wikipedia.org/wiki/Tagged_pointer -- /Jacob Carlborg
Apr 04
parent Dominikus Dittes Scherkl <dominikus scherkl.de> writes:
On Saturday, 4 April 2020 at 11:08:35 UTC, Jacob Carlborg wrote:
 On 2020-04-03 09:31, Dominikus Dittes Scherkl wrote:
 Has anybody ever considered to use bit-pointers?
Sounds like, or similar, to tagged pointers [1]
No, it's no special information stored together with the address. It IS the address. This is like the difference with memory segmentation and full pointers. Today the memory is still segmented - in bytes. But bit-pointers are designed to overcome this segmentation. Every bit is directly addressable.
Apr 05
prev sibling next sibling parent reply Basile B. <b2.temp gmx.com> writes:
On Friday, 3 April 2020 at 07:31:52 UTC, Dominikus Dittes Scherkl 
wrote:
 It was said that implementing bitarrays is complicated, because 
 of the indexing.

 Has anybody ever considered to use bit-pointers?
 Nobody really uses the full address range that 64bit pointers 
 have - in fact some hardware internally still uses 48bit or 
 56bit address-registers, so instead adding three lower address 
 bits would not cost a lot (just forward bit 3..58 to the 
 register instead of bit 0..55).
 This would also allow for implementing 2bit-types (one that I 
 really would appreciate, because it can represent sign values, 
 providing -1, 0, 1 and NaN - which is necessary as a comparison 
 result for non-ordered values), and 4bit-types (so called 
 nibbles).
 And with bit-pointers of course implementing arrays of boolean, 
 sign, nibbles or even odd-length types would be straight 
 forward. All the strange side-effects of byte clustering would 
 vanish.

 Just an idea.
Yes I already thought to that, using an addressing system relative to the base address of a memory pool with a fixed size. At some point I considered this for a very wasteful Radix-tree structure but never did. This would work with a kind of stdx.allocator-like static interface but the problem is that the pointers types become something like ubyte[1], ubyte[2], ubyte[3], etc. depending on the pool max size. But the stdx alloc interface take void[] (and works on void[].ptr). So all the helpers (make, makeArray, etc) would not be usable and finally you'd have to write a lot to make the things usable, I mean in a generic way, with all D types.
Apr 04
parent reply Dominikus Dittes Scherkl <dominikus scherkl.de> writes:
On Saturday, 4 April 2020 at 11:44:24 UTC, Basile B. wrote:
 Yes I already thought to that, using an addressing system 
 relative to the base address of a memory pool with a fixed size.

 At some point I considered this for a very wasteful Radix-tree 
 structure but never did.

 This would work with a kind of stdx.allocator-like static 
 interface but the problem is that the pointers types become 
 something like ubyte[1], ubyte[2], ubyte[3], etc. depending on 
 the pool max size. But the stdx alloc interface take void[] 
 (and works on void[].ptr).
No, I thought of a whole new type-system, where ALL pointers are bit-pointers, just the "standard" types now have to follow a byte-alignment (the address has to be divisable by 8 - like on 68000er, where all multi-byte types had to have even addresses).
 So all the helpers (make, makeArray, etc) would not be usable 
 and finally you'd have to write a lot to make the things 
 usable, I mean in a generic way, with all D types.
Yes, there is a lot to change. I came up with this idea now, because there's a discussion about D3, and this is something I wish for a new language.
Apr 05
parent Dominikus Dittes Scherkl <dominikus scherkl.de> writes:
On Sunday, 5 April 2020 at 10:46:18 UTC, Dominikus Dittes Scherkl 
wrote:
 I thought of a whole new type-system, where ALL pointers are 
 bit-pointers, just the "standard" types now have to follow a 
 byte-alignment (the address has to be divisible by 8 - like on 
 68000er, where all multi-byte types had to have even addresses).
Let me explain this a little further. Motorola learned, that sparing one address line was not worth the hussle that was not necessary on other architectures, so later on they added the missing line (in 60030). If now a language exists, that make good use of direct bit-addressing, some time later they may also be available in hardware, so the alignment requirement can be removed also. Segmentation may be a good idea if every line in hardware is extra ordinary expensive, but nowadays it should be no factor anymore. It's only a traditional bad habit to segment the memory into bytes.
Apr 05
prev sibling next sibling parent reply Faux Amis <faux amis.com> writes:
On 2020-04-03 09:31, Dominikus Dittes Scherkl wrote:
 It was said that implementing bitarrays is complicated, because of the 
 indexing.
 
 Has anybody ever considered to use bit-pointers?
 Nobody really uses the full address range that 64bit pointers have - in 
 fact some hardware internally still uses 48bit or 56bit 
 address-registers, so instead adding three lower address bits would not 
 cost a lot (just forward bit 3..58 to the register instead of bit 0..55).
 This would also allow for implementing 2bit-types (one that I really 
 would appreciate, because it can represent sign values, providing -1, 0, 
 1 and NaN - which is necessary as a comparison result for non-ordered 
 values), and 4bit-types (so called nibbles).
 And with bit-pointers of course implementing arrays of boolean, sign, 
 nibbles or even odd-length types would be straight forward. All the 
 strange side-effects of byte clustering would vanish.
 
 Just an idea.
I see what you mean. The addressable space would be 8 times less (not a problem for the foreseeable future of course). No clue what implementations this would have though :)
Apr 05
parent Patrick Schluter <Patrick.Schluter bbox.fr> writes:
On Sunday, 5 April 2020 at 16:42:24 UTC, Faux Amis wrote:
 On 2020-04-03 09:31, Dominikus Dittes Scherkl wrote:
 It was said that implementing bitarrays is complicated, 
 because of the indexing.
 
 Has anybody ever considered to use bit-pointers?
 Nobody really uses the full address range that 64bit pointers 
 have - in fact some hardware internally still uses 48bit or 
 56bit address-registers, so instead adding three lower address 
 bits would not cost a lot (just forward bit 3..58 to the 
 register instead of bit 0..55).
 This would also allow for implementing 2bit-types (one that I 
 really would appreciate, because it can represent sign values, 
 providing -1, 0, 1 and NaN - which is necessary as a 
 comparison result for non-ordered values), and 4bit-types (so 
 called nibbles).
 And with bit-pointers of course implementing arrays of 
 boolean, sign, nibbles or even odd-length types would be 
 straight forward. All the strange side-effects of byte 
 clustering would vanish.
 
 Just an idea.
I see what you mean. The addressable space would be 8 times less (not a problem for the foreseeable future of course). No clue what implementations this would have though :)
D had bit pointer a long time ago (or it was seriously envisioned) in pre 1.0 times and Walter had said that it was waste of time. Complicates the compiler significantly for not much benefit. He referred to it recently and he was still hostile towards it.
Apr 05
prev sibling parent 9il <ilyayaroshenko gmail.com> writes:
On Friday, 3 April 2020 at 07:31:52 UTC, Dominikus Dittes Scherkl 
wrote:
 It was said that implementing bitarrays is complicated, because 
 of the indexing.

 Has anybody ever considered to use bit-pointers?
 Nobody really uses the full address range that 64bit pointers 
 have - in fact some hardware internally still uses 48bit or 
 56bit address-registers, so instead adding three lower address 
 bits would not cost a lot (just forward bit 3..58 to the 
 register instead of bit 0..55).
 This would also allow for implementing 2bit-types (one that I 
 really would appreciate, because it can represent sign values, 
 providing -1, 0, 1 and NaN - which is necessary as a comparison 
 result for non-ordered values), and 4bit-types (so called 
 nibbles).
 And with bit-pointers of course implementing arrays of boolean, 
 sign, nibbles or even odd-length types would be straight 
 forward. All the strange side-effects of byte clustering would 
 vanish.

 Just an idea.
Sure. 1. GC allocated bitarrays. 2. Ref-counted bitarrays 2. Bit array on top of a user-provided integer array. 3. Packed integer (1-65 bits) arrays on top of a user-provided integer array. 4. Packed bytes bytegroup arrays on top of a user-provided integer array. All of the provided API has random access range primitives, as well the types are ndslices. Thus mean you can have construct for example a bitmatrix. Have a good day :)
Apr 05