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


This goes for all numeric arrays as well.


-- 
-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. 


 This goes for all numeric arrays as well.


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