www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - BitArray/BitFields - Review

reply "Era Scarecrow" <rtcvb32 yahoo.com> writes:
BitFields:
https://github.com/rtcvb32/phobos/commit/729c96e2f20ddd0c05a1afb488030b5c4db3e012

new BitArray Overhead functions/templates:
https://github.com/rtcvb32/phobos/commit/55aaf82a39f3901f03f5f1ac26fd175c5b2cd167

BitArray:
https://github.com/rtcvb32/phobos/commit/568c0d1966208afe70cedcaddc3bb880dc3d481d

  I'd like opinions of the code I've submitted, and certain 
shortcomings that are present that appropriate changes would be 
needed to fix. Only one of these has been a problem during 
debugging and that's due to references. (All three patches must 
be present to work)

BitArray:
1) Slices use references (sometimes) to previous bitarray. Since 
it's a slice (like an array) this could be expected.
Solutions:
  a) Drop the union, make all functions  safe (compared to 
 trusted), and they are all ref/slices
  b) Leave as sometimes ref, sometimes not; Use .dup when you NEED 
to ensure different unique copies.
  c) Apply COW (Copy-On-Write) where a known slice type (canExpand 
is false) when a change would apply, it replaces the present 
slice into it's own unique array.
  d) All slices become new dup'ed allocated arrays (Most expensive 
of them all)

2) opCast disabled: Anyone using opCast their code will break, 
however depending on it's usage that may not be an issue. If 
anyone can recommend alternative opCast(s) that won't prevent 
normal use of casting, then they will be reimplemented.

3) dim - An artifact of the previous BitArray, and I think needs 
to be removed as it has limited use.

4) Certain operators (opCat, opCat_r) I can't replace with 
opBinary/opBinary_r.

5) Examples of additional use cases/construction that it 
currently fails and should work.

6) Added rawWrite (for primitives), usefulness testing and 
opinions.

7) opApply, toHash, opCmp, opEqual tested in various environments 
(Like associative arrays) for problems, along with any possible 
const issues.

BitFields:
  I've concentrated on adding default values. A set of functions 
previously present string functions 'myXXX' were present, why 
were they present to begin with? Was it a limitation of what was 
available at the time? Or was it to make compiling faster so it 
didn't rely on other library functions? Or were the string 
functions not available at the time? They might be removed once 
this is truly answered.

//currently should work
struct A
{
   mixin(bitfields!(
     uint, "x",    2,
     int,  "y",    3,
     uint, "z=1",  2,
     bool, "flag=true", 1));
}
A obj;
assert(obj.x == 0);
assert(obj.z == 1);    //default
assert(obj.flag == 1); //true/false should also work
Jul 28 2012
next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Saturday, July 28, 2012 22:41:48 Era Scarecrow wrote:

 2) opCast disabled: Anyone using opCast their code will break,
 however depending on it's usage that may not be an issue. If
 anyone can recommend alternative opCast(s) that won't prevent
 normal use of casting, then they will be reimplemented.



I'm not particularly familar with BitArray, so I don't know what its opCast 
would convert to, but opCast will only convert to the types that you let it, 
so if you need to constrain what types it works with, then use template 
constraints to do that. If, on the other hand, opCast just doesn't make any 
sense at all, then just don't have it.

- Jonathan M Davis
Jul 28 2012
prev sibling next sibling parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
On 29-Jul-12 00:41, Era Scarecrow wrote:

 BitFields:
 https://github.com/rtcvb32/phobos/commit/729c96e2f20ddd0c05a1afb488030b5c4db3e012


 new BitArray Overhead functions/templates:
 https://github.com/rtcvb32/phobos/commit/55aaf82a39f3901f03f5f1ac26fd175c5b2cd167


 BitArray:
 https://github.com/rtcvb32/phobos/commit/568c0d1966208afe70cedcaddc3bb880dc3d481d


   I'd like opinions of the code I've submitted, and certain shortcomings
 that are present that appropriate changes would be needed to fix. Only
 one of these has been a problem during debugging and that's due to
 references. (All three patches must be present to work)



Great! But I strongly suggest to repost it in d.D newsgroup as it has
wider audience and is more appropriate for reviews.


 BitArray:
 1) Slices use references (sometimes) to previous bitarray. Since it's a
 slice (like an array) this could be expected.
 Solutions:
   a) Drop the union, make all functions  safe (compared to  trusted),
 and they are all ref/slices
   b) Leave as sometimes ref, sometimes not; Use .dup when you NEED to
 ensure different unique copies.
   c) Apply COW (Copy-On-Write) where a known slice type (canExpand is
 false) when a change would apply, it replaces the present slice into
 it's own unique array.
   d) All slices become new dup'ed allocated arrays (Most expensive of
 them all)



My solution is make slices different type e.g. BitSlice.
It's always reference to the original BitArray. Array itself still can 
be either compact or not. All operations with slice go to array (and 
still check if they can use word-aligned speed up).

How does it sound?


 2) opCast disabled: Anyone using opCast their code will break, however
 depending on it's usage that may not be an issue. If anyone can
 recommend alternative opCast(s) that won't prevent normal use of
 casting, then they will be reimplemented.

 3) dim - An artifact of the previous BitArray, and I think needs to be
 removed as it has limited use.

 4) Certain operators (opCat, opCat_r) I can't replace with
 opBinary/opBinary_r.



opCat isn't it just operator "~" and "~=" ? You can use opOpAssign for 
"~=" IRC.


 5) Examples of additional use cases/construction that it currently fails
 and should work.

 6) Added rawWrite (for primitives), usefulness testing and opinions.

 7) opApply, toHash, opCmp, opEqual tested in various environments (Like
 associative arrays) for problems, along with any possible const issues.

 BitFields:
   I've concentrated on adding default values. A set of functions
 previously present string functions 'myXXX' were present, why were they
 present to begin with?



I suspect to!string wasn't CTFEable. Regardless you can catch a word 
from Andrei Alexandrescu on the main D newsgroup who (I think) came up 
with it in the first place.


-- 
Dmitry Olshansky
Jul 28 2012
next sibling parent Dmitry Olshansky <dmitry.olsh gmail.com> writes:
On 29-Jul-12 01:07, Jonathan M Davis wrote:

 On Sunday, July 29, 2012 00:58:59 Dmitry Olshansky wrote:

 My solution is make slices different type e.g. BitSlice.
 It's always reference to the original BitArray. Array itself still can
 be either compact or not. All operations with slice go to array (and
 still check if they can use word-aligned speed up).

 How does it sound?



 I would point out that while hasSlicing doesn't currently check for it, if
 opSlice doesn't return a type which is assignable to the original range, it
 won't work in a lot of Phobos functions. I keep meaning to bring that up for
 discussion in the main newsgroup.



BitArray isn't and shouldn't be a range. It's a container.
So BitSlice is a range over BitArray. What am I missing?



-- 
Dmitry Olshansky
Jul 28 2012
prev sibling parent Dmitry Olshansky <dmitry.olsh gmail.com> writes:
On 29-Jul-12 01:20, Era Scarecrow wrote:

 On Saturday, 28 July 2012 at 20:59:15 UTC, Dmitry Olshansky wrote:

 Great! But I strongly suggest to repost it in d.D newsgroup as it has
 wider audience and is more appropriate for reviews.



   I was thinking of not bothering Andrei or Walter while i fixed other
 issues on it before bringing more major ones forward (which is why i
 brought it to D.learn), but re-posting it there is easy enough


 My solution is make slices different type e.g. BitSlice. It's always
 reference to the original BitArray. Array itself still can be either
 compact or not. All operations with slice go to array (and still check
 if they can use word-aligned speed up).

 How does it sound?



   Someone else also suggested making the slice different (Meaning a new
 Bitarray always is at max compact size).



Obviously that was me (blackwhale) ;)

Since we need at least a single

 flag to determine if the array is compact or array reference, there
 would be a larger loss which the current offset/maxOffset handle quite
 nicely filling in that space.



Not sure I followed you - what with offset/maxOffset ? You mean less 
space available for compact version?

  Making BitSlice separate suggests BitArray

 would be the bare minimum (canUseBulk, length, and index operations)
 while bitSlice would handle all others. But if you do that, either
 BitSlice would have to be inherently convertible to BitArray if you want
 to pass it to a function that expects a BitArray.



Take a look at std.container from what I see there Array does have a 
separate range type.

I'm hesitant to do it,

 but if there's a strong enough argument for it I wouldn't refuse it.


 opCat isn't it just operator "~" and "~=" ? You can use opOpAssign for
 "~=" IRC.



   Yes, I think opAssign is used for ~= already, but doing the following
 requires opCat and opCat_r.

   BitArray a; //filled with something
   auto x = true ~ a;
   auto y = a ~ true;

   I just can't get it to accept it (for whatever reason). Compiler bug?





 I suspect to!string wasn't CTFEable. Regardless you can catch a word
 from Andrei Alexandrescu on the main D newsgroup who (I think) came up
 with it in the first place.



   If we can use the std.string functions I'll replace them all :) (As I
 was just following the theme since they were present).

   I'll move this to the D group and see what we get for this.




-- 
Dmitry Olshansky
Jul 28 2012
prev sibling next sibling parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Sunday, July 29, 2012 00:58:59 Dmitry Olshansky wrote:

 My solution is make slices different type e.g. BitSlice.
 It's always reference to the original BitArray. Array itself still can
 be either compact or not. All operations with slice go to array (and
 still check if they can use word-aligned speed up).
 
 How does it sound?



I would point out that while hasSlicing doesn't currently check for it, if 
opSlice doesn't return a type which is assignable to the original range, it 
won't work in a lot of Phobos functions. I keep meaning to bring that up for 
discussion in the main newsgroup. I'd argue that hasSlicing really be changed 
from

    enum bool hasSlicing = !isNarrowString!R && is(typeof(
    (inout int _dummy=0)
    {
        R r = void;
        auto s = r[1 .. 2];
        static assert(isInputRange!(typeof(s)));
    }));

to something like

    enum bool hasSlicing = !isNarrowString!R && is(typeof(
    (inout int _dummy=0)
    {
        R r = void;
        auto s = r[1 .. 2];
        static assert(isInputRange!(typeof(s)));
        r = s;
    }));

- Jonathan M Davis
Jul 28 2012
parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
On 29-Jul-12 01:39, Era Scarecrow wrote:

 On Saturday, 28 July 2012 at 21:30:21 UTC, Jonathan M Davis wrote:


 Well, it seems that my comment was somewhat misplaced in that BitArray
 isn't a range but a container. My comment was directed at opSlice on
 ranges. Container types should return whatever range type is
 appropriate. That will usually be a struct of some variety. I'd have
 to study BitArray and your changes to determine what the appropriate
 type was here, but it sounds like you were talking about duping the
 contents with opSlice, which would be highly irregular. Normally,
 ranges over containers are light wrappers which can iterate through
 and potentially alter the elements in the container, and duping up an
 array as the range type doesn't work like that. But depending on what
 BitArray is doing exactly, it might be appropriate. I don't know.



   An array suggests you can control the size of the array, however if
 you are forced to work in 32increments (or more if 64bit), that makes it
 highly hard to control without making it a slice to begin with. Consider
 without slices (range control)



A strange jump to conclusions? Why can't array know it's size in bits 
and capacity in words?


   BitArray ba; //size 32/64bit

   ba.length = 42; //life, the universe and everything
   assert(ba.length == 42); //fails, can't set length except by
 increments of 32/64

   ba ~= true; //what's the size now? Or are all appending operators
 invalid unless it's a slice?



43 ? Why should it use 32/64 bit increments?


   foreach(b; ba) {
     //fails, can't go over range.
   }



works as foreach takes [] when needed automagically :)

   auto slice = ba[]; //converts to BitSlice

   foreach(b; slice) {
      //works
   }

   BitSlice func(BitArray ba);
   BitSlice func(BitSlice ba); //two versions of function needed? If
 convertable between the two, then you only lose the begining/ending
 length offsets.



Just make it a template if it works with any range.


   T func(T)(T ba) if (is(T : BitArray)) // correct? Potential loss of
 information.



  if(isRandomAccessRange!R && is(Unqual!(ElementType!R) == bool))

Would be far more general. As a bonus it will work with built-in arrays 
of bool or anything compatible.


   BitSlice x = ba[1 .. 10];
   BitArray y = func(x); //range lost, beginning/ending at max regardless
 of size



Certain functions would need to take a BitArray if they need to change 
it size, append, prepand etc.


   Honestly that doesn't add up to what I call an 'array'. It should look
 like an array, act like an array, and besides not being able to specify
 the array as separate from the entire BitArray (Ie const(int)) it's
 otherwise should not be distinguishable from an array.



It's damn hard to emulate built-in array. And I'd rather not to see this 
emulation half-working.

And in say C++, std::vector (and most arrays in other languages I know 
about) is not sliceble at all or slices are different type, or they do 
copy the whole thing. So I'm not sure what kind of array you are used 
to.  D's built-in arrays are rare beasts with their own issues, even 
with the fair deal of built-in language/runtime support they have.

-- 
Dmitry Olshansky
Jul 28 2012
parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
On 29-Jul-12 02:08, Era Scarecrow wrote:

 On Saturday, 28 July 2012 at 21:49:45 UTC, Dmitry Olshansky wrote:

 On 29-Jul-12 01:39, Era Scarecrow wrote:

 An array suggests you can control the size of the array, however if
 you are forced to work in 32increments (or more if 64bit), that makes
 it highly hard to control without making it a slice to begin with.
 Consider without slices (range control)



 A strange jump to conclusions? Why can't array know it's size in bits
 and capacity in words?



   Knowing the size based on if it's compact or the array.length * bits
 would be easy, but to do slices you drop the beginning/ending reference
 pointers, locking it at 32/64bits.



Mhm? Not getting you it at all. What's locking it ?

What's wrong with:
struct BitArray
{

union {
	struct {
		size_t[] data;
		ulong length;	//in bits

//length in words would be just
// (length + size_t.sizeof*4) / // (size_t.sizeof*8);
// as it's a power of 2 it should get optimized

	}
	size_t[2+ulong.sizeof/size_t.sizeof] compact;

// and say 1 bit is used for isCompact would be great if it could use // 
the least significant bit of pointer from data[], dunno if it's easy enough
}

}

then Range would be:

struct Range{
	BitArray* array;
	ulong start, end;
}

to mark [start..end] piece of it?

If you keep that information, why not

 just include slicing along with the rest of it?



I'm not seeing slicing easily integrated just because length is known.

-- 
Dmitry Olshansky
Jul 28 2012
parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
On 29-Jul-12 02:31, Era Scarecrow wrote:

 On Saturday, 28 July 2012 at 22:19:05 UTC, Dmitry Olshansky wrote:

 Mhm? Not getting you it at all. What's locking it ?

 What's wrong with:
 struct BitArray
 {

 union {
     struct {
         size_t[] data;
         ulong length;    //in bits

 //length in words would be just
 // (length + size_t.sizeof*4) / // (size_t.sizeof*8);
 // as it's a power of 2 it should get optimized

     }
     size_t[2+ulong.sizeof/size_t.sizeof] compact;

 // and say 1 bit is used for isCompact would be great if it could use
 // the least significant bit of pointer from data[], dunno if it's
 easy enough



   I'd rather not rely on the pointer at all as a reference for if it's
 compact.



No problem, I redesigned a bit:

struct BitArray
{

union {
     struct {
         ulong length;    //in bits, the top bit used as isCompact
         size_t[] data;
     }
     struct{
	ushort smallLength; //here as well
	ubyte[size_t.sizeof*2+ulong.sizeof-2] compact;
     }
}

Up 2^63 of bits would occupy 2^60 of bytes should be good enough for the 
years to come.
  I'm not seeing it as a problem as at very least processors have to 
actually be able to address more then 42 (or was it 48?) bits that they 
can now. (see AMD or Intel or ARM datasheets on 64 bit chips)

If the array is changed later to a template that could accept

 bytes, then where does that leave you?
 When the slice doesn't need to
 know more of the beginning,



???
Slice can start at some random offset

  it can re-slice it to a lesser more

 appropriate size.



no idea what's you are talking about here.

  It may very well soon contain a third entry in the

 union for main operations and use the larger size_t just for canUseBulk
 (Actually that sounds better to me).



Again I'm having hard time to get what follows from where. Can you 
expand on this point please?
Preferably with some code as it was far easier to reason about.



   Besides, separating the slice suggests 'length' is not part of the
 union struct.



How? All containers know their length.

Sure it's convertible to [0 .. length], but it's no longer

 convertible back to BitArray (Unless you make a whole new array and
 conversion/copying which takes a lot of time).



Yes it's not convertible. And it's no problem and is intended. Otherwise 
like you said it doesn't make a lot of sense.


If you do that, why not
 do BitSlice from the beginning which holds BitArray, but then if you do
 that why make them separate at all?
 It doesn't make sense to me. I can
 see making a separate range for the front/popFront/empty if you really
 wanted to use those, but it wouldn't change how it would work.




 then Range would be:

 struct Range{
     BitArray* array;
     ulong start, end;
 }

 to mark [start..end] piece of it?


 If you keep that information, why not just include slicing along with
 the rest of it?



 I'm not seeing slicing easily integrated just because length is known.



   Beginning and ending are known, so slicing can be added at no extra cost.




-- 
Dmitry Olshansky
Jul 28 2012
parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
On 29-Jul-12 03:16, Era Scarecrow wrote:

 On Saturday, 28 July 2012 at 23:02:17 UTC, Dmitry Olshansky wrote:

 On 29-Jul-12 02:31, Era Scarecrow wrote:

 On Saturday, 28 July 2012 at 22:19:05 UTC, Dmitry Olshansky wrote:

 Mhm? Not getting you it at all. What's locking it ?

 What's wrong with:
 struct BitArray
 {

 union {
    struct {
        size_t[] data;
        ulong length;    //in bits

 //length in words would be just
 // (length + size_t.sizeof*4) / // (size_t.sizeof*8);
 // as it's a power of 2 it should get optimized

    }
    size_t[2+ulong.sizeof/size_t.sizeof] compact;

 // and say 1 bit is used for isCompact would be great if it could use
 // the least significant bit of pointer from data[], dunno if it's
 easy enough



 I'd rather not rely on the pointer at all as a reference for if it's
 compact.



 No problem, I redesigned a bit:

 struct BitArray
 {

 union {
     struct {
         ulong length;    //in bits, the top bit used as isCompact
         size_t[] data;
     }
     struct{
     ushort smallLength; //here as well
     ubyte[size_t.sizeof*2+ulong.sizeof-2] compact;
     }
 }

 Up 2^63 of bits would occupy 2^60 of bytes should be good enough for
 the years to come.
  I'm not seeing it as a problem as at very least processors have to
 actually be able to address more then 42 (or was it 48?) bits that
 they can now. (see AMD or Intel or ARM datasheets on 64 bit chips)



 2^63, or drop 8 so it takes up no more than 2^55 bytes of memory. Yes
 that's quite a large chunk.

   Curiously enough the current structure is already smaller than the
 proposed unions.



OK. Now back to the biggest question:
Slices use references (sometimes) to previous bitarray. Since it's a 
slice (like an array) this could be expected.

The "sometimes" part is not god enough! The problem is that small string 
optimization (or small array optimization) doesn't work with reference 
semantics. You may dig up discussion on proposal for small string 
optimization for char[] and string that was shot down on these grounds.
Bulit-in like semantics call for simple ptr/ptr+length struct and you 
can't get that can you?.

E.g.

void mess_with(BitArray ba)
{
ba ~= true;
ba ~= false;
  //does it change anything outside this function? *maybe*
ba[0] ^= true;
ba[1] ^= true;
auto x = ba; //even if used ref BitArray ba, x *maybe* references ba
//is x now a reference or a copy? *maybe*

}

Thus BitArray either becomes value type (that may come as unexpected, 
see your option c/d). Or it becomes full reference type as in option a 
(though it sucks).
Sorry but b is no go, as it makes code unpredictable I'd rather take my 
idea with separate ranges then b.

Solutions:
  a) Drop the union, make all functions  safe (compared to  trusted), 
and they are all ref/slices
  b) Leave as sometimes ref, sometimes not; Use .dup when you NEED to 
ensure different unique copies.
  c) Apply COW (Copy-On-Write) where a known slice type (canExpand is 
false) when a change would apply, it replaces the present slice into 
it's own unique array.
  d) All slices become new dup'ed allocated arrays (Most expensive of 
them all)

Because of d, I proposed that slices be separate type that is always a 
reference to original. Then only coping arrays themselves involves dup.


 Begin takes extra ulong I'm not sure it is needed in the container
 itself.



   No it doesn't. bitfields are used to handle the beginning/ending
 offsets, equaling a total of 14 bits. It's the most confusing part
 (aside from [offset + sliceoffset + i[ formulas). canExpand and
 isCompact fill the other two bits.



OK, finally I think I understand how your current version works. It's 
clever but leaves you in half-way value-reference state.

To point out few problems with unification of slice type and BitArray:

- Every time a small slice is taken say [1..30] it becomes a small 
array(?) thus it is a value type and doesn't affect original array

- No idea if a = b make a copy will make programmers nervous, esp if one 
is writing a library function as in this case there is no assumption 
that fits all

- Same thing but more, does this work?
	auto c = ba; //if ba is compact
	ba ~= true;
	assert(c.length = ba.length-1);
	//c should remain with the same length unaffected (at least like built 
in arrays)

-- 
Dmitry Olshansky
Jul 28 2012
parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
On 29-Jul-12 12:55, Era Scarecrow wrote:

 On Sunday, 29 July 2012 at 06:27:32 UTC, Dmitry Olshansky wrote:

 Thus BitArray either becomes value type (that may come as unexpected,
 see your option c/d). Or it becomes full reference type as in option a
 (though it sucks). Sorry but b is no go, as it makes code
 unpredictable I'd rather take my idea with separate ranges then b.



   I've had a thought. Why not make it fully reference and at the same
 time not? Consider making a slice which is the real BitArray, then you
 have an outer container that when you want value semantics you use it
 and it would make appropriate copies every time it needed to (including
 when first put in the container). It would be implicitly convertible to
 a slice. So...

 BitArraySlice {
    //real bitarray stuff and pointer ref
 }

 BitArray { //value semantics wrapper?
    BitArraySlice ba;
    alias ba this;

    //include wrapper versions of binary operators

    this(this) {
    }
 }

   Doing it this way the arguments being passed as reference slices would
 ensure unneeded copies wouldn't be made. On the other hand a smaller
 portion of the code would need to be updated. Along with that a slice
 could be set as COW allowing quite a bit of flexibility.

   Thoughts?



Hm... and small array optimizations go where? BitArraySlice won't be a 
full reference type if it does it.

-- 
Dmitry Olshansky
Jul 29 2012
parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
On 29-Jul-12 13:18, Era Scarecrow wrote:

 On Sunday, 29 July 2012 at 09:03:08 UTC, Dmitry Olshansky wrote:

 On 29-Jul-12 12:55, Era Scarecrow wrote:

 Doing it this way the arguments being passed as reference slices
 would ensure unneeded copies wouldn't be made. On the other hand a
 smaller portion of the code would need to be updated. Along with that
 a slice could be set as COW allowing quite a bit of flexibility.

  Thoughts?



 Hm... and small array optimizations go where? BitArraySlice won't be a
 full reference type if it does it.



   I was thinking about that; If need be the slice can point to another
 slice which holds the actual small array (Kinda a long workaround). The
 way to small array optimization to work would be if BitArray generated
 it, since when you go to slicing you either reference the original data
 in the slice, or you could drop the small array optimization; although a
 loss it would simplify code until you come back to it once the code is
 working the way it should.

   Another idea is to convert the struct into a class instead, which
 would allow some options, but won't be a perfect fit, and inheritance
 could be used; which would solve some of the small array optimization,
 but at what cost?



I have simpler suggestion. Maybe doing it as 2 containers:

BitSet is a plain value type with small array optimization (what you 
called BitArray in last 2 posts) and no slicing (only as opSlice() i.e. 
as a whole). Best used for small things under < 1000 bits (as even dup 
will be cheap enough).

BitArray is class or struct that has reference smenatics and drops small 
array optimization in favor of having simple & fast slicing
Best used for big arrays with no less then 100-200 bits.


-- 
Dmitry Olshansky
Jul 29 2012
next sibling parent Dmitry Olshansky <dmitry.olsh gmail.com> writes:
On 29-Jul-12 14:28, Era Scarecrow wrote:

 On Sunday, 29 July 2012 at 09:30:06 UTC, Dmitry Olshansky wrote:

 I have simpler suggestion. Maybe doing it as 2 containers:

 BitSet is a plain value type with small array optimization (what you
 called BitArray in last 2 posts) and no slicing (only as opSlice()
 I.e. as a whole). Best used for small things under < 1000 bits (as
 even dup will be cheap enough).

 BitArray is class or struct that has reference smenatics and drops
 small array optimization in favor of having simple & fast slicing Best
 used for big arrays with no less then 100-200 bits.



   As long as you only use one or the other then it sounds great; I'm
 sure a conversion/constructor would be available to convert from one to
 another. That does seem like the best solution, but also feels like
 we're building it twice (Little code re-use).



Yup.


   Might be a third option: A template struct that represents a BitArray
 type (with 90% of the code); you then insert a structure with key
 functions that would handle the value/reference & duplication part.



Sounds a lot like mixin template. I'd try to invent some small set of 
primitive operations and auto-magically construct the others from it.


   I'll meditate on it for a few days and see if anything pops up.



And just to keep your mind busy :) how about adding SIMD to speed it all up:
http://dlang.org/simd.html
It's kind of new & cool thing but not very well documented.

-- 
Dmitry Olshansky
Jul 29 2012
prev sibling parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
On 30-Jul-12 23:50, Era Scarecrow wrote:

 On Sunday, 29 July 2012 at 12:39:13 UTC, Era Scarecrow wrote:

  But having them statically separated by name/type seems much more
 likely to be safer in the long run with reliable results.



   A question regarding templates. A template with different parameters
 is completely incompatible correct? So...



Yeah, like twin brothers the have different IDs :)


 struct X(T) {
 }

 alias X!bool XB;
 alias X!int XI;

 void func(XB xb) {

 }

 func(XB()); //works
 func(XI()); //should fail to compile

 Same if it was built differently? so...

 template X(bool something) //'bool something' should be statically
 checkable
    struct XY {
      static if (something) {
        //conditional functions or code
      }
      XY makeX(){
        //XY type is only currently formed template version correct?
        return XY();
      }
    }
 }

 //against above func, with these two...
 alias X!(false).XY XB;
 alias X!(true).XY XI;

 Course if there's a way to avoid asking about the inner XY, I wonder how
 I would do that.


   Now if all that is correct, say I want to make two functions that both
 use X, but are not compatible, but template functions will allow it. So...

 void tempFunc(T, U)(T t, U u)
 if(
    //What do i enter to check they are both template X or struct XY? As
 signatures will be different...
 )
 body{
    //now acts as a middle-man to be compatible for said operation
 }



Not sure what you would like to accomplish here.


 alias X!(true).XY Xtrue;

 pure function 'func' cannot call impure function '__cpctor'
 safe function 'func' cannot call system function '__cpctor'



Yeah, it's a bug. File it please.

-- 
Dmitry Olshansky
Jul 30 2012
parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
On 31-Jul-12 01:03, Era Scarecrow wrote:

 On Monday, 30 July 2012 at 20:19:51 UTC, Dmitry Olshansky wrote:

 Not sure what you would like to accomplish here.



 Than an example...



You can go for simpler separation:

struct BitArray{
//() - is an empty template spec
	ref BitArrayopSliceAssign()(const BitArray ba, int start, int end)
{
//two bit array can try balk mode etc.


   Reminds me. Due to how rvalue/lvalues work, assuming I need to const
 reference something but I don't care if it's a temporary or not, would I
 then do...

 struct X {
    int opCmp(const X x) const { //catch temporary
      return opCmp(x); //becomes reference, as it's now named 'x'
    }
    int opCmp(const ref X x) const {
      //do work here
      return 0;
    }
 }

 X x;
 assert(x == x);   //ref
 assert(x == X()); //temporary

   course if the 'in' keyword is the key i will have to test that to make
 sure.




-- 
Dmitry Olshansky
Jul 30 2012
parent Dmitry Olshansky <dmitry.olsh gmail.com> writes:
On 31-Jul-12 02:40, Era Scarecrow wrote:

 On Monday, 30 July 2012 at 22:23:46 UTC, Era Scarecrow wrote:

 On Monday, 30 July 2012 at 21:56:20 UTC, Dmitry Olshansky wrote:

 in == scope const not sure what scope buys here but couldn't hurt.



 If it can avoid making a new copy, then it likely would help. I'll
 need to test it. I actually am not quite sure how scope works as an
 argument; it isn't really covered in TDPL from what I recall.



   Tests with 'in' doesn't help, only ref and catching a temporary seem
 to prevent postblits.



 Also the empty template doesn't work, somehow I'm not surprised...

 template X(bool something) {
   struct XT {



Fixed :


     void func(bool smth)(X!(smth).XT x){



By default XT is deduced as X!(current value of smth).XT


          writeln("XT template called: typeID:", typeid(x));
     }
   }
 }

 alias X!true.XT A;
 alias X!false.XT B;

 A a, b;
 B ba;

 a.func(b); //passes
 a.func(ba);

 Error: template test.X!(true).XT.func does not match any function
 template declaration
 Error: template test.X!(true).XT.func() cannot deduce template function
 from argument types !()(XT)




-- 
Dmitry Olshansky
Jul 30 2012
prev sibling next sibling parent "Era Scarecrow" <rtcvb32 yahoo.com> writes:
On Saturday, 28 July 2012 at 20:59:15 UTC, Dmitry Olshansky wrote:

 Great! But I strongly suggest to repost it in d.D newsgroup as 
 it has wider audience and is more appropriate for reviews.



  I was thinking of not bothering Andrei or Walter while i fixed 
other issues on it before bringing more major ones forward (which 
is why i brought it to D.learn), but re-posting it there is easy 
enough


 My solution is make slices different type e.g. BitSlice. It's 
 always reference to the original BitArray. Array itself still 
 can be either compact or not. All operations with slice go to 
 array (and still check if they can use word-aligned speed up).

 How does it sound?



  Someone else also suggested making the slice different (Meaning 
a new Bitarray always is at max compact size). Since we need at 
least a single flag to determine if the array is compact or array 
reference, there would be a larger loss which the current 
offset/maxOffset handle quite nicely filling in that space. 
Making BitSlice separate suggests BitArray would be the bare 
minimum (canUseBulk, length, and index operations) while bitSlice 
would handle all others. But if you do that, either BitSlice 
would have to be inherently convertible to BitArray if you want 
to pass it to a function that expects a BitArray. I'm hesitant to 
do it, but if there's a strong enough argument for it I wouldn't 
refuse it.


 opCat isn't it just operator "~" and "~=" ? You can use 
 opOpAssign for "~=" IRC.



  Yes, I think opAssign is used for ~= already, but doing the 
following requires opCat and opCat_r.

  BitArray a; //filled with something
  auto x = true ~ a;
  auto y = a ~ true;

  I just can't get it to accept it (for whatever reason). Compiler 
bug?


 I suspect to!string wasn't CTFEable. Regardless you can catch a 
 word from Andrei Alexandrescu on the main D newsgroup who (I 
 think) came up with it in the first place.



  If we can use the std.string functions I'll replace them all :) 
(As I was just following the theme since they were present).

  I'll move this to the D group and see what we get for this.
Jul 28 2012
prev sibling next sibling parent "Era Scarecrow" <rtcvb32 yahoo.com> writes:
On Saturday, 28 July 2012 at 21:07:31 UTC, Jonathan M Davis wrote:

 I would point out that while hasSlicing doesn't currently check 
 for it, if opSlice doesn't return a type which is assignable to 
 the original range, it won't work in a lot of Phobos functions. 
 I keep meaning to bring that up for discussion in the main 
 newsgroup. I'd argue that hasSlicing really be changed



  Which is one of the main reasons I am hesitant to have a 
separate range struct (of BitSlice)... Hmmm maybe we should keep 
it here for a little while, and talk it over a bit more.
Jul 28 2012
prev sibling next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Sunday, July 29, 2012 01:19:49 Dmitry Olshansky wrote:

 On 29-Jul-12 01:07, Jonathan M Davis wrote:

 On Sunday, July 29, 2012 00:58:59 Dmitry Olshansky wrote:

 My solution is make slices different type e.g. BitSlice.
 It's always reference to the original BitArray. Array itself still can
 be either compact or not. All operations with slice go to array (and
 still check if they can use word-aligned speed up).
 
 How does it sound?



 I would point out that while hasSlicing doesn't currently check for it, if
 opSlice doesn't return a type which is assignable to the original range,
 it
 won't work in a lot of Phobos functions. I keep meaning to bring that up
 for discussion in the main newsgroup.



 BitArray isn't and shouldn't be a range. It's a container.
 So BitSlice is a range over BitArray. What am I missing?



Probably nothing. I'm not all that familiar with BitArray. If it's not a 
range, it's not a problem. I assumed that it was and was just pointing out a 
potential problem based on that assumption.

- Jonathan M Davis
Jul 28 2012
prev sibling next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Saturday, July 28, 2012 23:23:30 Era Scarecrow wrote:

 On Saturday, 28 July 2012 at 21:07:31 UTC, Jonathan M Davis wrote:

 I would point out that while hasSlicing doesn't currently check
 for it, if opSlice doesn't return a type which is assignable to
 the original range, it won't work in a lot of Phobos functions.
 I keep meaning to bring that up for discussion in the main
 newsgroup. I'd argue that hasSlicing really be changed



   Which is one of the main reasons I am hesitant to have a
 separate range struct (of BitSlice)... Hmmm maybe we should keep
 it here for a little while, and talk it over a bit more.



Well, it seems that my comment was somewhat misplaced in that BitArray isn't a 
range but a container. My comment was directed at opSlice on ranges. Container 
types should return whatever range type is appropriate. That will usually be a 
struct of some variety. I'd have to study BitArray and your changes to 
determine what the appropriate type was here, but it sounds like you were 
talking about duping the contents with opSlice, which would be highly 
irregular. Normally, ranges over containers are light wrappers which can 
iterate through and potentially alter the elements in the container, and 
duping up an array as the range type doesn't work like that. But depending on 
what BitArray is doing exactly, it might be appropriate. I don't know.

- Jonathan M Davis
Jul 28 2012
prev sibling next sibling parent "Era Scarecrow" <rtcvb32 yahoo.com> writes:
On Saturday, 28 July 2012 at 21:30:21 UTC, Jonathan M Davis wrote:


 Well, it seems that my comment was somewhat misplaced in that 
 BitArray isn't a range but a container. My comment was directed 
 at opSlice on ranges. Container types should return whatever 
 range type is appropriate. That will usually be a struct of 
 some variety. I'd have to study BitArray and your changes to 
 determine what the appropriate type was here, but it sounds 
 like you were talking about duping the contents with opSlice, 
 which would be highly irregular. Normally, ranges over 
 containers are light wrappers which can iterate through and 
 potentially alter the elements in the container, and duping up 
 an array as the range type doesn't work like that. But 
 depending on what BitArray is doing exactly, it might be 
 appropriate. I don't know.



  An array suggests you can control the size of the array, however 
if you are forced to work in 32increments (or more if 64bit), 
that makes it highly hard to control without making it a slice to 
begin with. Consider without slices (range control)

  BitArray ba; //size 32/64bit

  ba.length = 42; //life, the universe and everything
  assert(ba.length == 42); //fails, can't set length except by 
increments of 32/64

  ba ~= true; //what's the size now? Or are all appending 
operators invalid unless it's a slice?

  foreach(b; ba) {
    //fails, can't go over range.
  }

  auto slice = ba[]; //converts to BitSlice

  foreach(b; slice) {
     //works
  }

  BitSlice func(BitArray ba);
  BitSlice func(BitSlice ba); //two versions of function needed? 
If convertable between the two, then you only lose the 
begining/ending length offsets.

  T func(T)(T ba) if (is(T : BitArray)) // correct? Potential loss 
of information.

  BitSlice x = ba[1 .. 10];
  BitArray y = func(x); //range lost, beginning/ending at max 
regardless of size



  Honestly that doesn't add up to what I call an 'array'. It 
should look like an array, act like an array, and besides not 
being able to specify the array as separate from the entire 
BitArray (Ie const(int)) it's otherwise should not be 
distinguishable from an array.
Jul 28 2012
prev sibling next sibling parent "Era Scarecrow" <rtcvb32 yahoo.com> writes:
On Saturday, 28 July 2012 at 21:39:56 UTC, Era Scarecrow wrote:

 BitArray (Ie const(int)) it's otherwise should not be



  My filter/formatter got me again...

   Honestly that doesn't add up to what I call an 'array'. It 
should look like an array, act like an array, and besides not 
being able to specify the array as separate from the entire 
BitArray (ie: const(int)[]) it's otherwise should be 
indistinguishable from an array template-wise.
Jul 28 2012
prev sibling next sibling parent "Era Scarecrow" <rtcvb32 yahoo.com> writes:
On Saturday, 28 July 2012 at 21:49:45 UTC, Dmitry Olshansky wrote:

 On 29-Jul-12 01:39, Era Scarecrow wrote:

 An array suggests you can control the size of the array, 
 however if you are forced to work in 32increments (or more if 
 64bit), that makes it highly hard to control without making it 
 a slice to begin with. Consider without slices (range control)



 A strange jump to conclusions? Why can't array know it's size 
 in bits and capacity in words?



  Knowing the size based on if it's compact or the array.length * 
bits would be easy, but to do slices you drop the 
beginning/ending reference pointers, locking it at 32/64bits. If 
you keep that information, why not just include slicing along 
with the rest of it?


  BitArray ba; //size 32/64bit

  ba.length = 42; //life, the universe and everything
  assert(ba.length == 42); //fails, can't set length except by
 increments of 32/64

  ba ~= true; //what's the size now? Or are all appending 
 operators
 invalid unless it's a slice?



 43 ? Why should it use 32/64 bit increments?



  See above.


 works as foreach takes [] when needed automagically :)



  I thought about that after I submitted it, so my mistake on that.


 Just make it a template if it works with any range.

 T func(R)(R ba)
  if(isRandomAccessRange!R && is(Unqual!(ElementType!R) == bool))

 Would be far more general. As a bonus it will work with 
 built-in arrays of bool or anything compatible.



  True, but you'd still need to specifically convert the array to 
a slice first. So you'd call it func(ba[]), or func(ba.range) or 
func(ba[0 .. $]). Kinda seems silly to require the extra bit 
there.


  BitSlice x = ba[1 .. 10];
  BitArray y = func(x); //range lost, beginning/ending at max 
 regardless
 of size



 change it size, append, prepand etc.



  See first reply.


 It's damn hard to emulate built-in array. And I'd rather not to 
 see this emulation half-working.

 And in say C++, std::vector (and most arrays in other languages 
 I know about) is not sliceble at all or slices are different 
 type, or they do copy the whole thing. So I'm not sure what 
 kind of array you are used to. D's built-in arrays are rare 
 beasts with their own issues, even with the fair deal of 
 built-in language/runtime support they have.



  Obviously it can't emulate it perfectly, but doing all the basic 
operations should be acceptable. I don't know all of what arrays 
require, but opIndex and length are the largest part to my 
opinion, which I guess is just randomAccessRange (or whatever 
it's called)
Jul 28 2012
prev sibling next sibling parent "Era Scarecrow" <rtcvb32 yahoo.com> writes:
On Saturday, 28 July 2012 at 22:19:05 UTC, Dmitry Olshansky wrote:

 Mhm? Not getting you it at all. What's locking it ?

 What's wrong with:
 struct BitArray
 {

 union {
 	struct {
 		size_t[] data;
 		ulong length;	//in bits

 //length in words would be just
 // (length + size_t.sizeof*4) / // (size_t.sizeof*8);
 // as it's a power of 2 it should get optimized

 	}
 	size_t[2+ulong.sizeof/size_t.sizeof] compact;

 // and say 1 bit is used for isCompact would be great if it 
 could use // the least significant bit of pointer from data[], 
 dunno if it's easy enough



  I'd rather not rely on the pointer at all as a reference for if 
it's compact. If the array is changed later to a template that 
could accept bytes, then where does that leave you? When the 
slice doesn't need to know more of the beginning, it can re-slice 
it to a lesser more appropriate size. It may very well soon 
contain a third entry in the union for main operations and use 
the larger size_t just for canUseBulk (Actually that sounds 
better to me).

  Besides, separating the slice suggests 'length' is not part of 
the union struct. Sure it's convertible to [0 .. length], but 
it's no longer convertible back to BitArray (Unless you make a 
whole new array and conversion/copying which takes a lot of 
time). If you do that, why not do BitSlice from the beginning 
which holds BitArray, but then if you do that why make them 
separate at all? It doesn't make sense to me. I can see making a 
separate range for the front/popFront/empty if you really wanted 
to use those, but it wouldn't change how it would work.


 then Range would be:

 struct Range{
 	BitArray* array;
 	ulong start, end;
 }

 to mark [start..end] piece of it?


 If you keep that information, why not just include slicing 
 along with the rest of it?



 I'm not seeing slicing easily integrated just because length is 
 known.



  Beginning and ending are known, so slicing can be added at no 
extra cost.
Jul 28 2012
prev sibling next sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Era Scarecrow:


 BitFields:
  I've concentrated on adding default values.



Good, that's useful.


Regarding BitArray I have written some ER:

http://d.puremagic.com/issues/show_bug.cgi?id=4123
http://d.puremagic.com/issues/show_bug.cgi?id=4124
http://d.puremagic.com/issues/show_bug.cgi?id=4717
http://d.puremagic.com/issues/show_bug.cgi?id=7487
http://d.puremagic.com/issues/show_bug.cgi?id=7488
http://d.puremagic.com/issues/show_bug.cgi?id=7490

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

Bye,
bearophile
Jul 28 2012
parent Don Clugston <dac nospam.com> writes:
On 29/07/12 23:36, bearophile wrote:

 Era Scarecrow:




 Another commonly needed operation is a very fast bit count. There 










  Likely similar to the hamming weight table mentioned in TDPL.
 Combined with the canUseBulk I think I could make it fairly fast.



 There is lot of literature about implementing this operation
 efficiently. For the first implementation a moderately fast (and short)
 code is probably enough. Later faster versions of this operation will go
 in Phobos, coming from papers.



See bug 4717. On x86, even on 32 bits you can get close to 1 cycle per 
byte, on 64 bits you can do much better.
Jul 31 2012
prev sibling next sibling parent "Era Scarecrow" <rtcvb32 yahoo.com> writes:
On Saturday, 28 July 2012 at 22:43:22 UTC, bearophile wrote:

 Era Scarecrow:


 BitFields:
 I've concentrated on adding default values.



 Good, that's useful.


 Regarding BitArray I have written some ER:

 http://d.puremagic.com/issues/show_bug.cgi?id=4123
 http://d.puremagic.com/issues/show_bug.cgi?id=4124
 http://d.puremagic.com/issues/show_bug.cgi?id=4717
 http://d.puremagic.com/issues/show_bug.cgi?id=7487
 http://d.puremagic.com/issues/show_bug.cgi?id=7488
 http://d.puremagic.com/issues/show_bug.cgi?id=7490



4123 - fixed
4124 - Set/reset all bits ie:
   BitArray ba = BitArray(100);
   ba[] = true;
Others haven't been done yet.

4717 - Same as 4124, none others done yet.
7487 - Done. When prepending it extends the array to size_t extra 
and slowly backtracks until it needs to do it again. To go 
further, have to disable re-slicing of the allocated array.

Or perhaps a 'start at end' during constructor stage. Hmmm..

7488 - Done, union used and is 'compact' version (by default or 
resized and can fit)

7490 - haven't touched yet. :(


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



  Not so sure. Could make a multi-dimentional one that returns 
slices to various sections, but  that's iffy. I'd need an example 
of how you'd use it with BitArray before I could build a solution.
Jul 28 2012
prev sibling next sibling parent "Era Scarecrow" <rtcvb32 yahoo.com> writes:
On Saturday, 28 July 2012 at 23:02:17 UTC, Dmitry Olshansky wrote:

 On 29-Jul-12 02:31, Era Scarecrow wrote:

 On Saturday, 28 July 2012 at 22:19:05 UTC, Dmitry Olshansky 
 wrote:

 Mhm? Not getting you it at all. What's locking it ?

 What's wrong with:
 struct BitArray
 {

 union {
    struct {
        size_t[] data;
        ulong length;    //in bits

 //length in words would be just
 // (length + size_t.sizeof*4) / // (size_t.sizeof*8);
 // as it's a power of 2 it should get optimized

    }
    size_t[2+ulong.sizeof/size_t.sizeof] compact;

 // and say 1 bit is used for isCompact would be great if it 
 could use
 // the least significant bit of pointer from data[], dunno if 
 it's easy enough



 I'd rather not rely on the pointer at all as a reference for 
 if it's compact.



 No problem, I redesigned a bit:

 struct BitArray
 {

 union {
     struct {
         ulong length;    //in bits, the top bit used as 
 isCompact
         size_t[] data;
     }
     struct{
 	ushort smallLength; //here as well
 	ubyte[size_t.sizeof*2+ulong.sizeof-2] compact;
     }
 }

 Up 2^63 of bits would occupy 2^60 of bytes should be good 
 enough for the years to come.
  I'm not seeing it as a problem as at very least processors 
 have to actually be able to address more then 42 (or was it 
 48?) bits that they can now. (see AMD or Intel or ARM 
 datasheets on 64 bit chips)



2^63, or drop 8 so it takes up no more than 2^55 bytes of memory. 
Yes that's quite a large chunk.

  Curiously enough the current structure is already smaller than 
the proposed unions.


 If the array is changed later to a template that could accept 
 bytes, then where does that leave you? When the slice doesn't 
 need to know more of the beginning,







 ???
 Slice can start at some random offset



  Yes they can, but so can a normal array (as they are pretty much 
the same)


  it can re-slice it to a lesser more appropriate size.



 no idea what's you are talking about here.



  As for requested compact to hold the starting/ending offsets at 
1 byte each, obviously slicing at say 1024 to 2048 of a 10,000 
length bit array, that won't work (0-127). If it's larger than 
size_t in bits, it will subtract that size and internally change 
the pointer of the array it actually points to, until it can fit 
that new value.

start/end slice: [32 .. 64]
equals: size_t array[1 .. 2]


 It may very well soon contain a third entry in the union for 
 main operations and use the larger size_t just for canUseBulk 
 (Actually that sounds better to me).



 Again I'm having hard time to get what follows from where. Can 
 you expand on this point please? Preferably with some code as 
 it was far easier to reason about.



A question earlier was brought up about endienness for the patch, 
that is not part of what it can handle, so:

ba[100] = 1; //then save the array
assert(ba[100]); //fails on opposite endienness when loaded

HOWEVER! if individual bits are handled in a byte array 
reference, then the above would succeed, even with the larger 
size_t ones all working with canUseBulk.


 Besides, separating the slice suggests 'length' is not part of 
 the union struct.



 How? All containers know their length.



  Yes they do, they also know where they start, thereby giving 
start/ending, which allows slicing. So why separate slicing?


 Sure it's convertible to [0 .. length], but it's no longer 
 convertible back to BitArray (Unless you make a whole new 
 array and conversion/copying which takes a lot of time).



 Yes it's not convertible. And it's no problem and is intended. 
 Otherwise like you said it doesn't make a lot of sense.




 If you do that, why not do BitSlice from the beginning which 
 holds BitArray, but then if you do that why make them 
 separate at all? It doesn't make sense to me. I can see 
 making a separate range for the front/popFront/empty if you 
 really wanted to use those, but it wouldn't change how it 
 would work.










 Begin takes extra ulong I'm not sure it is needed in the 
 container itself.



  No it doesn't. bitfields are used to handle the beginning/ending 
offsets, equaling a total of 14 bits. It's the most confusing 
part (aside from [offset + sliceoffset + i[ formulas). canExpand 
and isCompact fill the other two bits.
Jul 28 2012
prev sibling next sibling parent "Era Scarecrow" <rtcvb32 yahoo.com> writes:
On Sunday, 29 July 2012 at 06:27:32 UTC, Dmitry Olshansky wrote:

 OK. Now back to the biggest question:
 Slices use references (sometimes) to previous bitarray. Since 
 it's a slice (like an array) this could be expected.

 The "sometimes" part is not god enough! The problem is that 
 small string optimization (or small array optimization) doesn't 
 work with reference semantics. You may dig up discussion on 
 proposal for small string optimization for char[] and string 
 that was shot down on these grounds.




 Bulit-in like semantics call for simple ptr/ptr+length struct 
 and you can't get that can you?.>
 E.g.

 void mess_with(BitArray ba)
 {
 ba ~= true;
 ba ~= false;
  //does it change anything outside this function? *maybe*



If it was a previous slice, then it never chances outside and 
appending would automatically allocate new memory.


 ba[0] ^= true;
 ba[1] ^= true;
 auto x = ba; //even if used ref BitArray ba, x *maybe* 
 references ba
 //is x now a reference or a copy? *maybe*

 Thus BitArray either becomes value type (that may come as 
 unexpected, see your option c/d). Or it becomes full reference 
 type as in option a (though it sucks).




 Sorry but b is no go, as it makes code unpredictable I'd rather 
 take my idea with separate ranges then b.




 Solutions:
  a) Drop the union, make all functions  safe (compared to 
  trusted), and they are all ref/slices
  b) Leave as sometimes ref, sometimes not; Use .dup when you 
 NEED to ensure different unique copies.
  c) Apply COW (Copy-On-Write) where a known slice type 
 (canExpand is false) when a change would apply, it replaces the 
 present slice into it's own unique array.
  d) All slices become new dup'ed allocated arrays (Most 
 expensive of them all)



  Agreed, B is a bad choice. I'm going to suggest c myself, as 
changes would only propagate to a new true copy, otherwise it's 
read-only as a slice.


 Because of d, I proposed that slices be separate type that is 
 always a reference to original. Then only coping arrays 
 themselves involves dup.



  Mmmm... i think you're right...


 No it doesn't. bitfields are used to handle the 
 beginning/ending offsets, equaling a total of 14 bits. It's 
 the most confusing part (aside from [offset + sliceoffset + i] 
 formulas). canExpand and isCompact fill the other two bits.



 OK, finally I think I understand how your current version 
 works. It's clever but leaves you in half-way value-reference 
 state.



  I didn't want to originally use the 1-byte per 
startBit/endingBit, but it does actually work when you have the 
functions working.


 To point out few problems with unification of slice type and 
 BitArray:

 - Every time a small slice is taken say [1..30] it becomes a 
 small array(?) thus it is a value type and doesn't affect 
 original array



  No, slices of compact arrays remain compact arrays. slices of 
larger arrays are reference until length is set, dupped, or 
appended to (forcing a resize/dup)


 - No idea if a = b make a copy will make programmers nervous, 
 esp if one is writing a library function as in this case there 
 is no assumption that fits all



  If it's compact, it's an auto separate copy/valuetype. If it's 
not compact, it's a reference to the original.


 - Same thing but more, does this work?
 	auto c = ba; //if ba is compact
 	ba ~= true;



  ba may or may not be a normal/compact at this point


 	assert(c.length = ba.length-1);
 	//c should remain with the same length unaffected (at least 
 like built in arrays)



  Most likely it would be compact afterwards (Even if it allocated 
memory).

  I guess after going this over, two things need to happen. First 
it needs to be non-reference type, I don't want to go option d 
route, so I'll go for c instead. On a copy I'll add a postblit 
that makes the 'copy' now a slice which will create a new array 
when it changes in any way. Only question is when you pass the 
BitArray to a function as you showed, it would still think it's 
the original, unless the postblit/opAssign (or similar) can 
handle that. Hmmm time for some testing.
Jul 29 2012
prev sibling next sibling parent "Era Scarecrow" <rtcvb32 yahoo.com> writes:
On Sunday, 29 July 2012 at 06:27:32 UTC, Dmitry Olshansky wrote:

 Thus BitArray either becomes value type (that may come as 
 unexpected, see your option c/d). Or it becomes full reference 
 type as in option a (though it sucks). Sorry but b is no go, as 
 it makes code unpredictable I'd rather take my idea with 
 separate ranges then b.



  I've had a thought. Why not make it fully reference and at the 
same time not? Consider making a slice which is the real 
BitArray, then you have an outer container that when you want 
value semantics you use it and it would make appropriate copies 
every time it needed to (including when first put in the 
container). It would be implicitly convertible to a slice. So...

BitArraySlice {
   //real bitarray stuff and pointer ref
}

BitArray { //value semantics wrapper?
   BitArraySlice ba;
   alias ba this;

   //include wrapper versions of binary operators

   this(this) {
   }
}

  Doing it this way the arguments being passed as reference slices 
would ensure unneeded copies wouldn't be made. On the other hand 
a smaller portion of the code would need to be updated. Along 
with that a slice could be set as COW allowing quite a bit of 
flexibility.

  Thoughts?
Jul 29 2012
prev sibling next sibling parent "Era Scarecrow" <rtcvb32 yahoo.com> writes:
On Sunday, 29 July 2012 at 09:03:08 UTC, Dmitry Olshansky wrote:

 On 29-Jul-12 12:55, Era Scarecrow wrote:

 Doing it this way the arguments being passed as reference 
 slices would ensure unneeded copies wouldn't be made. On the 
 other hand a smaller portion of the code would need to be 
 updated. Along with that a slice could be set as COW allowing 
 quite a bit of flexibility.

  Thoughts?



 Hm... and small array optimizations go where? BitArraySlice 
 won't be a full reference type if it does it.



  I was thinking about that; If need be the slice can point to 
another slice which holds the actual small array (Kinda a long 
workaround). The way to small array optimization to work would be 
if BitArray generated it, since when you go to slicing you either 
reference the original data in the slice, or you could drop the 
small array optimization; although a loss it would simplify code 
until you come back to it once the code is working the way it 
should.

  Another idea is to convert the struct into a class instead, 
which would allow some options, but won't be a perfect fit, and 
inheritance could be used; which would solve some of the small 
array optimization, but at what cost?
Jul 29 2012
prev sibling next sibling parent "Era Scarecrow" <rtcvb32 yahoo.com> writes:
On Sunday, 29 July 2012 at 09:30:06 UTC, Dmitry Olshansky wrote:

 I have simpler suggestion. Maybe doing it as 2 containers:

 BitSet is a plain value type with small array optimization 
 (what you called BitArray in last 2 posts) and no slicing (only 
 as opSlice() I.e. as a whole). Best used for small things under 
 < 1000 bits (as even dup will be cheap enough).

 BitArray is class or struct that has reference smenatics and 
 drops small array optimization in favor of having simple & fast 
 slicing Best used for big arrays with no less then 100-200 bits.



  As long as you only use one or the other then it sounds great; 
I'm sure a conversion/constructor would be available to convert 
from one to another. That does seem like the best solution, but 
also feels like we're building it twice (Little code re-use).

  Might be a third option: A template struct that represents a 
BitArray type (with 90% of the code); you then insert a structure 
with key functions that would handle the value/reference & 
duplication part.

  I'll meditate on it for a few days and see if anything pops up.
Jul 29 2012
prev sibling next sibling parent "Era Scarecrow" <rtcvb32 yahoo.com> writes:
On Sunday, 29 July 2012 at 10:34:50 UTC, Dmitry Olshansky wrote:

 Might be a third option: A template struct that represents a 
 BitArray type (with 90% of the code); you then insert a 
 structure with key functions that would handle the 
 value/reference & duplication part.



 Sounds a lot like mixin template. I'd try to invent some small 
 set of primitive operations and auto-magically construct the 
 others from it.



  Pretty much...  syntactical sugar, just add tea (T) I made a 
funny! :D


 I'll meditate on it for a few days and see if anything pops up.



 And just to keep your mind busy :) how about adding SIMD to 
 speed it all up:
 http://dlang.org/simd.html
 It's kind of new & cool thing but not very well documented.



  Mmm I'll look it over. If it can work for larger bulk operations 
I don't see why not.
Jul 29 2012
prev sibling next sibling parent "Era Scarecrow" <rtcvb32 yahoo.com> writes:
On Sunday, 29 July 2012 at 09:30:06 UTC, Dmitry Olshansky wrote:

 I have simpler suggestion. Maybe doing it as 2 containers:

 BitSet is a plain value type with small array optimization 
 (what you called BitArray in last 2 posts) and no slicing (only 
 as opSlice() I.e. as a whole). Best used for small things under 
 < 1000 bits (as even dup will be cheap enough).

 BitArray is class or struct that has reference semantics and 
 drops small array optimization in favor of having simple & fast 
 slicing Best used for big arrays with no less then 100-200 bits.



  Another thought coming to mind, is to have the BitArray with a 
few different modes it could operate in. One of the modes could 
be 'reference' which would make slices and them all work exactly 
as you would expect, while with referencing off it would act as a 
normal value type struct, since the mode/flags would modify how 
the postblit and assignment operators worked, along with the 
length. (Reference wouldn't use small array optimization).

  But having them statically separated by name/type seems much 
more likely to be safer in the long run with reliable results.
Jul 29 2012
prev sibling next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
Era Scarecrow:

As you guess I have had to use many arrays of bits in my programs 
:-)


 4124 - Set/reset all bits ie:
   BitArray ba = BitArray(100);
   ba[] = true;
 Others haven't been done yet.



Among those 4124 suggestions the most important, and very simple 
to implement, are:
- set n-th bit (this can be a little more efficient than bs[n]=1;)
- reset n-th bit (this can be a little more efficient than 
bs[n]=1;)

Another commonly needed operation is a very fast bit count. There 
are very refined algorithms to do this.



 7487 - Done. When prepending it extends the array to size_t 
 extra and slowly backtracks until it needs to do it again.



Leaving a bit of "capacity" at the beginning is a good idea.



 7488 - Done, union used and is 'compact' version (by default or 
 resized and can fit)



Good, this makes BitArray usable in many other situations :-)



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



  Not so sure. Could make a multi-dimentional one that returns 
 slices to various sections, but  that's iffy. I'd need an 
 example of how you'd use it with BitArray before I could build 
 a solution.



I have needed many times a fast BitMatrix, but I see it as a data 
structure distinct from BitArray, so don't worry about making 
them inter-operate.

For me a BitMatrix must be as fast as possible, even if this 
causes some waste of memory (see my implementation in the attach 
of issue 6697) and I use it for medium and large bit matrices. 
Generally I don't to count the set bits in a bit matrix. So the 
two data structures need different capabilities and they are 
better implemented in different ways (this means a FastBitMatrix 
is not an array of a BitArray!).

Taking a row of a FastBitMatrix and turning it into a a BitArray 
sounds cute, but generally I don't need to do this operation, so 
I don't care about this feature.

Bye,
bearophile
Jul 29 2012
prev sibling next sibling parent "Era Scarecrow" <rtcvb32 yahoo.com> writes:
On Sunday, 29 July 2012 at 14:41:48 UTC, bearophile wrote:

 As you guess I have had to use many arrays of bits in my 
 programs :-)



  I'll do what I can :)


 4124 - Set/reset all bits ie:
  BitArray ba = BitArray(100);
  ba[] = true;
 Others haven't been done yet.



 Among those 4124 suggestions the most important, and very 
 simple to implement, are:
 - set n-th bit (this can be a little more efficient than 
 bs[n]=1;)
 - reset n-th bit (this can be a little more efficient than 
 bs[n]=1;)



  If it has to determine between compact and non-compact, then I 
really don't see how any speed improvement can be made, and if 
it's optimized it may be inlined which would be about as fast as 
you could get.


 Another commonly needed operation is a very fast bit count. 
 There are very refined algorithms to do this.



  Likely similar to the hamming weight table mentioned in TDPL. 
Combined with the canUseBulk I think I could make it fairly fast.


 7487 - Done. When prepending it extends the array to size_t 
 extra and slowly backtracks until it needs to do it again.



 Leaving a bit of "capacity" at the beginning is a good idea.



  With how it's made for speed and slices, it had to :P


 7488 - Done, union used and is 'compact' version (by default 
 or resized and can fit)



 Good, this makes BitArray usable in many other situations :-)



  Yes, currently a debate of it's partial ref/value issue is 
coming up. As it is it's usable, and if you want to be sure it's 
unique you can always dup it, otherwise as a previous suggestion 
I'll either make two array types for either full reference vs 
value, or take his separate slices (reference) idea.


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



 Not so sure. Could make a multi-dimentional one that returns 
 slices to various sections, but  that's iffy. I'd need an 
 example of how you'd use it with BitArray before I could build 
 a solution.



 I have needed many times a fast BitMatrix, but I see it as a 
 data structure distinct from BitArray, so don't worry about 
 making them inter-operate.



  A Matrix is just a multidimensional array right? I'll have to 
read up on it a bit; doing simple division (Likely whole rows of 
32bit at a time) would do that job, but expanding width several 
times (compared to height) would be quite a bit slower; Although 
not too horrible.


 For me a BitMatrix must be as fast as possible, even if this 
 causes some waste of memory (see my implementation in the 
 attach of issue 6697) and I use it for medium and large bit 
 matrices. Generally I don't to count the set bits in a bit 
 matrix. So the two data structures need different capabilities 
 and they are better implemented in different ways (this means a 
 FastBitMatrix is not an array of a BitArray!).



  more likely bool array/matrix.. Although if you heavily use 
specific lines it could convert to bool[], and then back again, 
but if you go all over the place it would be worse than just 
using bool[].


 Taking a row of a FastBitMatrix and turning it into a a 
 BitArray sounds cute, but generally I don't need to do this 
 operation, so I don't care about this feature.
Jul 29 2012
prev sibling next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
Era Scarecrow:


  If it has to determine between compact and non-compact, then I 
 really don't see how any speed improvement can be made,



Maybe it's better to consider two use cases: dynamic length 
allocated on the heap (or allocated with a given allocator, often 
a stack-styled allocator), and fixed-size allocated in place, so 
there's no need for that run-time test.



 and if it's optimized it may be inlined which would be about as 
 fast as you could get.



I think that  "a[x] = 1;"  is slower than  "a.set(x);"  even if 
the array a is allocated in place and everything is inlined. This 
is probably the most important operation an array of bits has to 
support. If this is missing, I have to use my own implementation 
still.



  Likely similar to the hamming weight table mentioned in TDPL. 
 Combined with the canUseBulk I think I could make it fairly 
 fast.



There is lot of literature about implementing this operation 
efficiently. For the first implementation a moderately fast (and 
short) code is probably enough. Later faster versions of this 
operation will go in Phobos, coming from papers.



  Yes, currently a debate of it's partial ref/value issue is 
 coming up. As it is it's usable, and if you want to be sure 
 it's unique you can always dup it, otherwise as a previous 
 suggestion I'll either make two array types for either full 
 reference vs value, or take his separate slices (reference) 
 idea.



The idea of making two different types (for the dynamic and 
static versions) sounds nice.

There is a third use case, that is bit arrays that start small 
and can grow, and rarely grow bigger than one or two words. This 
asks for a dynamic-length bit array type that allocates locally 
only when it's small (so it needs to perform run-time test of the 
tag. Too bad the D GC doesn't support tagged pointers!). But 
probably this use case is not common enough to require a third 
type of array. So I suggest to not worry about this case now, and 
to focus on the other two more common ones.



  A Matrix is just a multidimensional array right?



Well, yes, but there are many ways to implement arrays and nD 
arrays. Sometimes the implementations differ.



 I'll have to read up on it a bit; doing simple division (Likely 
 whole rows of 32bit at a time) would do that job,



Take a look at my implementation in Bugzilla :-) It's another 
type, the third. The 1D and 2D cases are the most common.



 but expanding width several times (compared to height) would be 
 quite a bit slower; Although not too horrible.



A 2D array of bits probably doesn't need to change its size after 
creation, this is not a common use case.



  more likely bool array/matrix.. Although if you heavily use 
 specific lines it could convert to bool[], and then back again, 
 but if you go all over the place it would be worse than just 
 using bool[].



It's not so simple :-) A bool[] causes many more cache misses, if 
the matrix is not tiny. A bool[] or bool[][] is a good idea only 
if the matrix is very small, or if you don't have a bit matrix 
library and you don't want to write lot of code. Converting to 
bool[] the current line is not a good idea.

Bye,
bearophile
Jul 29 2012
prev sibling next sibling parent "Era Scarecrow" <rtcvb32 yahoo.com> writes:
On Sunday, 29 July 2012 at 12:39:13 UTC, Era Scarecrow wrote:

  But having them statically separated by name/type seems much 
 more likely to be safer in the long run with reliable results.



  A question regarding templates. A template with different 
parameters is completely incompatible correct? So...

struct X(T) {
}

alias X!bool XB;
alias X!int XI;

void func(XB xb) {

}

func(XB()); //works
func(XI()); //should fail to compile

Same if it was built differently? so...

template X(bool something) //'bool something' should be 
statically checkable
   struct XY {
     static if (something) {
       //conditional functions or code
     }
     XY makeX(){
       //XY type is only currently formed template version correct?
       return XY();
     }
   }
}

//against above func, with these two...
alias X!(false).XY XB;
alias X!(true).XY XI;

Course if there's a way to avoid asking about the inner XY, I 
wonder how I would do that.


  Now if all that is correct, say I want to make two functions 
that both use X, but are not compatible, but template functions 
will allow it. So...

void tempFunc(T, U)(T t, U u)
if(
   //What do i enter to check they are both template X or struct 
XY? As signatures will be different...
)
body{
   //now acts as a middle-man to be compatible for said operation
}


  Finally, I came across an anomaly and may just be a bug. What 
about a postblits?


T func2(T)(T x)  safe pure {
   return T();
}

struct XY {
   this(this)  safe pure {} //safe pure added so func can call it
   void func(XY x)  safe pure {
     XY y = x; //postblits called on all three lines
     func2(x);
     func2(y);
   }
}

template X(bool something) {
struct XY {
     this(this)  safe pure {}
     void func(XY x)  safe pure {
       XY y = x; //Error: see below
       func2(x);
       func2(y);
     }
   }
}

alias X!(true).XY Xtrue;

pure function 'func' cannot call impure function '__cpctor'
safe function 'func' cannot call system function '__cpctor'
Jul 30 2012
prev sibling next sibling parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
On Mon, Jul 30, 2012 at 9:50 PM, Era Scarecrow <rtcvb32 yahoo.com> wrote:


  A question regarding templates. A template with different parameters is
 completely incompatible correct?



Correct. They have no reason, in general, too even generate the same code:

template Chameleon(T)
{
    static if (is(T == struct))
        enum Chameleon = "I'm a string!"; // Chamelon!(SomeStruct) is
a string value
    else static if (is(T == class))
        void Chameleon(int i) { return i+1;} // Chameleon!(SomeClass)
is a function
    else
        alias T[int] Chameleon; // Here Chameleon is a type
}

The same for you struct S(T) { ... }. Inside the braces, anything can
happen (mwwaahhha hhaa!), depending on T.


 So...

 struct X(T) {
 }

 alias X!bool XB;
 alias X!int XI;

 void func(XB xb) {

 }

 func(XB()); //works
 func(XI()); //should fail to compile



Yes.


  Now if all that is correct, say I want to make two functions that both use
 X, but are not compatible, but template functions will allow it. So...



I'm not sure I understand what you're trying to do. Do you mean you
want a function that accept X!(T)s for any T, and not any other type?

struct X(T) {}

void func(T)(X!T x)
{}

void main()
{
    X!bool b;
    X!int i;
    func(b);
    func(i);
}


 void tempFunc(T, U)(T t, U u)
 if(
   //What do i enter to check they are both template X or struct XY? As
 signatures will be different...
 )
 body{
   //now acts as a middle-man to be compatible for said operation
 }



Here you want a constraint that checks that U and T are both
X!(SomeType) or an XY?

void tempFunc(T,U)(T t, U u) if (is(T a == X!(SomeType), SomeType) &&
is(U a == X!(SomeType), SomeType)
                                                || is(T == XY) && is(U == XY))
{
...
}


Is that what you need?
Jul 30 2012
prev sibling next sibling parent "Era Scarecrow" <rtcvb32 yahoo.com> writes:
On Monday, 30 July 2012 at 20:19:51 UTC, Dmitry Olshansky wrote:

 Not sure what you would like to accomplish here.



Than an example...

struct BitArray { //assume template...
   ref BitArray opSliceAssign(T)(const T ba, int start, int end)
   if (
    //if T is type bitArray but only a different change regarding 
parameters
    //we can use canUseBulk and other speedups. Otherwise a range 
is required.
    //checking all possibilities seems silly, but possible
   )
   body {
     //slice specific speedup and code
     return this;
   }
   int opEquals(T)(const T ba) const
   //if constraint as above
   body {}
}

Code wise; If BitSet is always value semantics and BitArray is 
always reference (a previous post) and slices/groups work 
basically the same; then...

BitSet bs = BitSet(100);
BitArray ba = BitArray(100);

  bs[0 .. 10] = ba[0 .. 10]; //should work
  assert(bs[0 .. 10] == ba[0 .. 10]); //should also be possible to 
work.


 alias X!(true).XY Xtrue;

 pure function 'func' cannot call impure function '__cpctor'
 safe function 'func' cannot call system function '__cpctor'



 Yeah, it's a bug. File it please.



Alright... Considered a major (Maybe even blocking).

  Reminds me. Due to how rvalue/lvalues work, assuming I need to 
const reference something but I don't care if it's a temporary or 
not, would I then do...

struct X {
   int opCmp(const X x) const { //catch temporary
     return opCmp(x); //becomes reference, as it's now named 'x'
   }
   int opCmp(const ref X x) const {
     //do work here
     return 0;
   }
}

X x;
assert(x == x);   //ref
assert(x == X()); //temporary

  course if the 'in' keyword is the key i will have to test that 
to make sure.
Jul 30 2012
prev sibling next sibling parent "Era Scarecrow" <rtcvb32 yahoo.com> writes:
On Monday, 30 July 2012 at 21:03:39 UTC, Era Scarecrow wrote:

 Alright... Considered a major (Maybe even blocking).



http://d.puremagic.com/issues/show_bug.cgi?id=8475
Jul 30 2012
prev sibling next sibling parent "Era Scarecrow" <rtcvb32 yahoo.com> writes:
On Monday, 30 July 2012 at 20:48:26 UTC, Philippe Sigaud wrote:

 Now if all that is correct, say I want to make two functions 
 that both use X, but are not compatible, but template 
 functions will allow it. So...



 I'm not sure I understand what you're trying to do. Do you mean 
 you want a function that accept X!(T)s for any T, and not any 
 other type?



  Anything of template X! previous post of mine shows sort of an 
example.


 struct X(T) {}

 void func(T)(X!T x)
 {}

 void main()
 {
     X!bool b;
     X!int i;
     func(b);
     func(i);
 }



  Hmmm i do think that seems right... but if it contains multiple 
parameters, then...?

template X(x1, x2, x3) {
  struct XT {}
}


 void func(T)(X!T x) {}





 Here you want a constraint that checks that U and T are both
 X!(SomeType) or an XY?



  As before, of Template X, and struct XY, but T (or sometype) 
doesn't matter.


 void tempFunc(T,U)(T t, U u) if (is(T a == X!(SomeType), 
 SomeType) &&
 is(U a == X!(SomeType), SomeType)
                                                 || is(T == XY) 
 && is(U == XY))
 {
 ...
 }
 Is that what you need?



  I want to say no... But I haven't actually tested it for my use 
cases. Leaving it unconstrained (without checking) to make it 
work is a disaster waiting to happen: I want T and U to both be 
of the same template (X in this case) but not the same 
instantiation arguments.

  I hope I'm not repeating myself too much.
Jul 30 2012
prev sibling next sibling parent "Era Scarecrow" <rtcvb32 yahoo.com> writes:
On Monday, 30 July 2012 at 21:56:20 UTC, Dmitry Olshansky wrote:

 You can go for simpler separation:

 struct BitArray{
 //() - is an empty template spec
 	ref BitArrayopSliceAssign()(const BitArray ba, int start, int 
 end)
 {
 //two bit array can try balk mode etc.



  I'll give it a try, it may very well be what I need; although I 
wouldn't have thought you could declare it like that. I have much 
to learn in the ways of the template.


  course if the 'in' keyword is the key i will have to test 
 that to make sure.



 hurt.



  If it can avoid making a new copy, then it likely would help. 
I'll need to test it. I actually am not quite sure how scope 
works as an argument; it isn't really covered in TDPL from what I 
recall.
Jul 30 2012
prev sibling next sibling parent "Era Scarecrow" <rtcvb32 yahoo.com> writes:
On Monday, 30 July 2012 at 22:23:46 UTC, Era Scarecrow wrote:

 On Monday, 30 July 2012 at 21:56:20 UTC, Dmitry Olshansky wrote:

 in == scope const not sure what scope buys here but couldn't 
 hurt.



 If it can avoid making a new copy, then it likely would help. 
 I'll need to test it. I actually am not quite sure how scope 
 works as an argument; it isn't really covered in TDPL from what 
 I recall.



  Tests with 'in' doesn't help, only ref and catching a temporary 
seem to prevent postblits.



Also the empty template doesn't work, somehow I'm not surprised...

template X(bool something) {
  struct XT {
    void func()(XT x){
         writeln("XT template called: typeID:", typeid(x));
    }
  }
}

alias X!true.XT A;
alias X!false.XT B;

A a, b;
B ba;

a.func(b); //passes
a.func(ba);

Error: template test.X!(true).XT.func does not match any function 
template declaration
Error: template test.X!(true).XT.func() cannot deduce template 
function from argument types !()(XT)
Jul 30 2012
prev sibling next sibling parent "Era Scarecrow" <rtcvb32 yahoo.com> writes:
On Monday, 30 July 2012 at 22:44:21 UTC, Dmitry Olshansky wrote:

 Fixed :


    void func(bool smth)(X!(smth).XT x){



 By default XT is deduced as X!(current value of smth).XT



Doesn't really fix it...

     a.func(b); //65 - doesn't match declaration.
     a.func(ba); //66
     //other template tests not worth putting, 67-70
     a.func!true(b); //71 - explicitly stated
     a.func!false(ba); //72
     a.func!false(b); //73 - Backwards on purpose for test
     a.func!true(ba); //74

(65): Error: template test.X!(true).XT.func does not match any 
function template declaration
(11): Error: template test.X!(true).XT.func(bool smth) cannot 
deduce template function from argument types !()(XT)

(66): Error: template test.X!(true).XT.func does not match any 
function template declaration
(11): Error: template test.X!(true).XT.func(bool smth) cannot 
deduce template function from argument types !()(XT)

(73): Error: function test.X!(true).XT.func!(false).func (XT x) 
is not callable using argument types (XT)
(73): Error: cannot implicitly convert expression (b) of type XT 
to XT
(74): Error: function test.X!(true).XT.func!(true).func (XT x) is 
not callable using argument types (XT)
(74): Error: cannot implicitly convert expression (ba) of type XT 
to XT
Jul 30 2012
prev sibling next sibling parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
On Mon, Jul 30, 2012 at 11:19 PM, Era Scarecrow <rtcvb32 yahoo.com> wrote:


 void func(T)(X!T x)
 {}

 void main()
 {
     X!bool b;
     X!int i;
     func(b);
     func(i);
 }




  Hmmm i do think that seems right... but if it contains multiple parameters,
 then...?

 template X(x1, x2, x3) {
  struct XT {}
 }


 void func(T)(X!T x) {}



 Will this still work?



No. Use a 3-params template or a tuple:

void func(A,B,C)(X!(A,B,C) x) {}

or

void func(Ts...)(X!(Ts) x) {}

or even, more general:

void func(T)(T x) if (is(T t = X!(SomeTypes), SomeTypes...)), because
template constrains are much more powerful and general than fiddling
arguments types.

There was a discussion between Simen Kjaeraas and me on the subject
not long ago. Kenji Hara extended the functionnality of is( , T...)
and did a pull request. I'm not sure it's in 2.060, the request was
done a week ago.



 void tempFunc(T,U)(T t, U u) if (is(T a == X!(SomeType), SomeType) &&
 is(U a == X!(SomeType), SomeType)
                                                 || is(T == XY) && is(U ==
 XY))
 {
 ...
 }
 Is that what you need?




  I want to say no... But I haven't actually tested it for my use cases.
 Leaving it unconstrained (without checking) to make it work is a disaster
 waiting to happen: I want T and U to both be of the same template (X in this
 case) but not the same instantiation arguments.



Said like this, it's much more clear for me :)

Note that in the above code, SomeType is a fresh variable in each is()
expression. So, even though I used the same name (shouldn't have done
that), T and U can have different type parameters.

*shameless plug*
Btw, I wrote a tutorial on templates, you can find it here:

https://github.com/PhilippeSigaud/D-templates-tutorial/blob/master/dtemplates.pdf

(click on 'view raw', that should download the pdf)

That should shed some light on the matters at hand.
Jul 30 2012
prev sibling next sibling parent "Era Scarecrow" <rtcvb32 yahoo.com> writes:
On Tuesday, 31 July 2012 at 05:27:58 UTC, Philippe Sigaud wrote:

 No. Use a 3-params template or a tuple:

 void func(A,B,C)(X!(A,B,C) x) {}
 or
 void func(Ts...)(X!(Ts) x) {}



  I don't know how many arguments it will have (depends on how 
many options I give it), and I honestly don't; It should be 
invisible for the end user as long as we can get the the 
constraints properly accepted.


 or even, more general:

 void func(T)(T x) if (is(T t = X!(SomeTypes), SomeTypes...)), 
 because template constrains are much more powerful and general 
 than fiddling arguments types.



  That doesn't make sense; but I don't have a full grasp of the 
templates (continued below).


 There was a discussion between Simen Kjaeraas and me on the 
 subject not long ago. Kenji Hara extended the functionnality of 
 is( , T...) and did a pull request. I'm not sure it's in 2.060, 
 the request was done a week ago.



  so the (, T...) is shorthand for testing the template type with 
multiple arguments. Nice. So multiple arguments would be...

  struct X (T, U) {}

  if(is(T t = X!(bool, bool), (int, int), (int, bool)))  //?


 I want to say no... But I haven't actually tested it for my 
 use cases. Leaving it unconstrained (without checking) to make 
 it work is a disaster waiting to happen: I want T and U to 
 both be of the same template (X in this case) but not the same 
 instantiation arguments.



 Said like this, it's much more clear for me :)

 Note that in the above code, SomeType is a fresh variable in 
 each is() expression. So, even though I used the same name 
 (shouldn't have done that), T and U can have different type 
 parameters.




 *shameless plug*
 Btw, I wrote a tutorial on templates, you can find it here:

 https://github.com/PhilippeSigaud/D-templates-tutorial/blob/master/dtemplates.pdf

 (click on 'view raw', that should download the pdf)
 That should shed some light on the matters at hand.



  Indeed... I remember glancing through it, but never really 
needed it badly; Now it seems I do. At least it's not C++ and 
it's templates. I'll be reading up on them starting tonight (and 
printing most of it); It is after all the hardest part (and most 
powerful part) of the language :P
Jul 30 2012
prev sibling next sibling parent "Era Scarecrow" <rtcvb32 yahoo.com> writes:
  Currently since I've been concentrating more on bitfields and 
BitArray needs more work, the two separate patches and trees are 
out of sync and apparently the auto-tester brings them up as a 
fail. How do I remove one of the pulls so I can concentrate on 
the one set of features and continue the others later?

  (Course I could just update what I have for BitArray so it works 
as a value-type for now too...)
Aug 02 2012
prev sibling next sibling parent "David Nadlinger" <see klickverbot.at> writes:
On Thursday, 2 August 2012 at 11:11:58 UTC, Era Scarecrow wrote:

 How do I remove one of the pulls so I can concentrate on the 
 one set of features and continue the others later?



Hm? You can just close pull requests (button at the bottom of the 
page), and reopen them later.

David
Aug 02 2012
prev sibling next sibling parent "Era Scarecrow" <rtcvb32 yahoo.com> writes:
On Thursday, 2 August 2012 at 11:26:42 UTC, David Nadlinger wrote:

 On Thursday, 2 August 2012 at 11:11:58 UTC, Era Scarecrow wrote:

 How do I remove one of the pulls so I can concentrate on the 
 one set of features and continue the others later?



 Hm? You can just close pull requests (button at the bottom of 
 the Page), and reopen them later.



  Most of this doesn't make sense to me still; just one of those 
things I'll learn as I use it over the next few years. Anyways 
when the bitfields are as updated as we're going to make it, I'll 
resume work on BitArray code.

  In the meantime I guess I'll check on the auto-tester once it 
refreshes.
Aug 02 2012
prev sibling next sibling parent "Era Scarecrow" <rtcvb32 yahoo.com> writes:
Following from issue list:

bearophile_hugs 2010-10-04 18:16:44 PDT

Another possible feature is to make std.bitmanip.bitfields 
generate two



to the CPU
endianess:


 static if (std.system.endian == std.system.Endian.BigEndian) {
    ...
 } else {
     ...
 }



Having it endian specific brings up a couple questions.

  Which endian is 'correct'? Resolutions could be...
   a) Both are correct (Leave as is)
   b) big/little is correct and should always convert to the other 
(which one?)
   c) Specify correct type as a flag, then swaps for the other in 
generated code

  Second, which would be the best approach?
   a) swap bytes in a temporary, modify the temporary, replace 
storage? (In every function)
   b) use current endianness, then prepping saving/loading have it 
swap? (very unlikely)
   c) use ubyte array and use shifting on each byte (small Endian, 
also allows for odd byte sizes, not very likely, but possible)

  I know an instruction for the Pentium system (686+?) bswap will 
swap the appropriate bytes as a conversion and takes a single 
cycle, using assembler that can be incorporated assuming it's 
ready for it (course than the template would be updated more 
likely and not the bitfield template).
Aug 02 2012
prev sibling next sibling parent "Era Scarecrow" <rtcvb32 yahoo.com> writes:
repost from issue list:

Austin Hastings 2010-09-24 18:06:53 PDT

 Also, I think I'm going to request that repeated bitfield 
 definitions be allowed if they are identical - I'd like to 
 redeclare "opcode" rather than "".



How would you tell them apart? If I know how you may want to call 
them, I may
be able to make something. I can understand with registers, but 
still need some
way to work with them. Perhaps as a set then?


 So I would like the bitmanip code to permit redeclaration of 
 bitfields that are identical in all respects.




 That is, obviously the names are the same, but the field width, 
 offset, and type representation has to be the same as well.



Maybe....?

struct S {
     mixin(bitfields!(
         uint, "opcode", 4,
         uint, "register", 4,
         uint, "register", 4,
         uint, "register", 4
     ));
}

and using the registers would have function signature like...

struct Register {
   uint register_1;
   uint register_2;
   uint register_3;

}

//setters, likely can't be  propery
void register(uint reg1, uint reg2, uint reg3);
void register(uint[] register ...); //maybe?
void register(Register register);

//getter ??
Register register() const;

Or perhaps...

struct S {
     mixin(bitfields!(
         uint, "opcode", 4,
         uint, "reg1", 4,
         uint, "reg2", 4,
         uint, "reg3", 4
     ));
     mixin(sharedNameSet(
         "nameForGetterAndSetter",
         "struct name for returning/passing",
         "reg1", "reg2", "reg3" //named variables as a set
     ));

     //nameForGetterAndSetter's would be added here, perhaps as 
above.
}
Aug 02 2012
prev sibling parent "Era Scarecrow" <rtcvb32 yahoo.com> writes:
On Thursday, 2 August 2012 at 11:26:42 UTC, David Nadlinger wrote:

 Hm? You can just close pull requests (button at the bottom of 
 the Page), and reopen them later.



  So I've removed the pull, but the auto tester is still pulling 
both code sources, so it's failing automatically because of it. 
Do I close the bitfields pull too? Or do I open another/new pull 
for it?
Aug 03 2012