www.digitalmars.com         C & C++   DMDScript  

D - Bit arrays for sets

reply dslate patrec.com writes:
D looks well thought out and does appear to address many of the
deficiencies of C and C++.  So I wish the developers luck in getting
it widely adopted.

I like the idea of "bit arrays", but it seems to me that perhaps
something is missing from their specification.  The Pascal language
didn't have a lot going for it, but it did have some good ideas, one
of which was "set of", which created a type of sets whose members were
values of some enumerated type.  The nice thing about "set of" was
that it was a high-level concept which could be implemented very
efficiently in hardware using bit arrays and boolean operations like
AND, OR, XOR, COMPLEMENT, etc.

When I saw that D had bit arrays, I thought that perhaps it would be
convenient to use them to implement these kinds of sets.  But although
D, like other C-like languages, does support the necessary low-level
boolean machine instructions, they take the integer types, not bit
arrays, as args.  D even has bsf() and bsr(), which are also useful in
connection with sets, but again they only take integer args.

Of course one could easily implement these bit array sets in D as
structs (or classes) using arrays of integers of the appropriate
number and size.  I have done this in C and C++ (for applications like
computer chess programs and genetic algorithms), and in D it should be
even easier, given the wise decision to specify exactly the bit
lengths of the various integer types.  But it would be even cleaner
and probably more efficient if this could be done with bit arrays,
which are a more natural fit to the set concept, since the programmer
would only have to specify the number of elements, and would not have
to be concerned with the details of dividing the bit array into some
number of ulongs or uints.  I would think that this could be done
without changes to the core language by implementing the set
operations as library functions on bit arrays, the calls to which could
be expanded inline for efficiency.


-- Dave Slate
Apr 23 2004
parent reply "Y.Tomino" <demoonlit inter7.jp> writes:
I agree.
Walter, please implement bit operations for bit array. 

YT
Apr 24 2004
parent reply J Anderson <REMOVEanderson badmama.com.au> writes:
Y.Tomino wrote:

I agree.
Walter, please implement bit operations for bit array. 

YT

-- -Anderson: http://badmama.com.au/~anderson/
Apr 24 2004
parent reply Ilya Minkov <minkov cs.tum.edu> writes:
J Anderson schrieb:
 Y.Tomino wrote:
 
I agree.
Walter, please implement bit operations for bit array. 


Aren't you both suggesting work which need not be neecessary done now? Now it is important to get D 1.0 out, then extend specification. For now, it could be a library. Later, it is better be supported by a set of intrinsics. I recall to already have suggested somewhat the same as David Slate a long while ago, and Walter did not comment on it. -eye
Apr 24 2004
parent reply J Anderson <REMOVEanderson badmama.com.au> writes:
Ilya Minkov wrote:

 Aren't you both suggesting work which need not be neecessary done now? 
 Now it is important to get D 1.0 out, then extend specification.

 For now, it could be a library. Later, it is better be supported by a 
 set of intrinsics.

 I recall to already have suggested somewhat the same as David Slate a 
 long while ago, and Walter did not comment on it.

 -eye

I can't remember where, but in the specs somewhere Walter mentions operator operations on arrays. It seems to me, it's just something that hasn't been done yet. -- -Anderson: http://badmama.com.au/~anderson/
Apr 24 2004
next sibling parent David J. Slate <David_member pathlink.com> writes:
In article <c6dhsn$2ok7$1 digitaldaemon.com>, J Anderson says...
Ilya Minkov wrote:

 Aren't you both suggesting work which need not be neecessary done now? 
 Now it is important to get D 1.0 out, then extend specification.

 For now, it could be a library. Later, it is better be supported by a 
 set of intrinsics.

 I recall to already have suggested somewhat the same as David Slate a 
 long while ago, and Walter did not comment on it.

 -eye

I can't remember where, but in the specs somewhere Walter mentions operator operations on arrays. It seems to me, it's just something that hasn't been done yet. -- -Anderson: http://badmama.com.au/~anderson/

It seems to me that library functions that implemented set operations on bit arrays would in some sense fill a bigger gap than implementing numeric operations on numeric arrays. The latter would be a convenient shorthand for loops that users could write themselves, but would not necessarily produce a significant efficiency gain. But performing operations on bit arrays using loops that process one bit at a time would be much less efficient than using the hardware (AND, OR, XOR, etc.) instructions that process many bits at a time. Those instructions are of course accessible in D, but not for bit array operations that could benefit from them. -- Dave Slate dslate patrec.com
Apr 26 2004
prev sibling parent reply Ilya Minkov <minkov cs.tum.edu> writes:
J Anderson schrieb:

 I can't remember where, but in the specs somewhere Walter mentions 
 operator operations on arrays.  It seems to me, it's just something that 
 hasn't been done yet.

You are right. There is a reason why they are in a spec. Having that would allow to write a vectorizing compiler fairly trivially - especially interesing for the GNU project, since GCC cannot vectorize itself, but has reserved intrinsics for optimized vector operations for major platforms where they apply! I brought up the question on vectorization after IRCing with some gurus, and Walter's answer was that as i thought the whole-array operations are exactly for that. -eye
Apr 27 2004
parent J Anderson <REMOVEanderson badmama.com.au> writes:
Ilya Minkov wrote:

 J Anderson schrieb:

 I can't remember where, but in the specs somewhere Walter mentions 
 operator operations on arrays.  It seems to me, it's just something 
 that hasn't been done yet.

You are right. There is a reason why they are in a spec. Having that would allow to write a vectorizing compiler fairly trivially - especially interesing for the GNU project, since GCC cannot vectorize itself, but has reserved intrinsics for optimized vector operations for major platforms where they apply! I brought up the question on vectorization after IRCing with some gurus, and Walter's answer was that as i thought the whole-array operations are exactly for that. -eye

Yeah optimisation is the reason I want them to. They need not be optimised now, but some time in the future they could. -- -Anderson: http://badmama.com.au/~anderson/
Apr 27 2004