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