Re: BitArray/BitFields - Review
On 29/07/12 23:36, bearophile wrote: Era Scarecrow: >>> 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. 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.
Re: sorting failed error
I now tried to bring it to the next level, using concurrency to bread a couple of populations and make the best solutions migrate between them. But, to use concurrency in D, one has to continually cast between immutable, cast immutable away, Not only that, casting away from immutable (or too, the error message is not informative at all) you get error's along the line of "opEquals doesn't work with immutable arguments"... Why is it that cumbersome? It seems like D took a good idea and ruined it with all that const-stuff. I have the feeling that I've completely missed the whole idea on how concurrency in D should work. Is it normal that you have to either mess with immutable or with the broken shared? Am I implementing everything wrong?
Re: sorting failed error
On Tuesday, July 31, 2012 11:41:19 maarten van damme wrote: > I now tried to bring it to the next level, using concurrency to bread > a couple of populations and make the best solutions migrate between > them. > But, to use concurrency in D, one has to continually cast between > immutable, cast immutable away, > Not only that, casting away from immutable (or too, the error message > is not informative at all) you get error's along the line of "opEquals > doesn't work with immutable arguments"... > > Why is it that cumbersome? It seems like D took a good idea and ruined > it with all that const-stuff. > > I have the feeling that I've completely missed the whole idea on how > concurrency in D should work. Is it normal that you have to either > mess with immutable or with the broken shared? > Am I implementing everything wrong? To pass something across threads, it either needs to be a value type, or shared, or immutable. Unfortunately, shared doesn't work std.concurrency right now though, so you're stuck using immutable. What we really need is a way to indicate that ownership is being passed from one thread to another, but that can't really be done with the current type system. However, there are probably tweaks that can be made to make it more pleasant to deal with. As for "messing it up with const", immutability (and therefore const) is a core part of D's threading model. By making everything thread-local by default, you then need a way to share instances across threads, and that requires shared (and immutable is implicitly shared). And with immutable, that can be done much more efficiently, because then the compiler doesn't have to worry about multiple threads screwing with the variable. So, the situation isn't perfect and still needs some work, but the basic idea is solid and does work, even if it deosn't yet work quite as well as we'd like. - Jonathan M Davis
Re: Detector for unused variables
I agree that having the compiler make warnings about unused variables is a really good idea!!! Java has it and when I program in eclipse it's really useful because the editor can highlight the particular lines.
Re: Why must bitfields sum to a multiple of a byte?
On Tuesday, 31 July 2012 at 00:44:16 UTC, Andrej Mitrovic wrote: On 7/31/12, Era Scarecrow wrote: It assumes the largest type we can currently use which is ulong Ah yes, it makes sense now. Thanks for the brain cereal. :p I saw your bug report: http://d.puremagic.com/issues/show_bug.cgi?id=8474 The bug is only when the field is EXACTLY 32 bits BTW. bitfields works quite nice with 33 or whatever. More details in the report.
Re: Detector for unused variables
On 07/31/2012 11:55 AM, Minas wrote: I agree that having the compiler make warnings about unused variables is a really good idea!!! Java has it and when I program in eclipse it's really useful because the editor can highlight the particular lines. An editor can be configured to point it out even if it is not in the language, if it is considered useful.
Re: Why must bitfields sum to a multiple of a byte?
On 7/31/12, monarch_dodra wrote: > The bug is only when the field is EXACTLY 32 bits BTW. bitfields > works quite nice with 33 or whatever. More details in the report. Yeah 32 or 64 bits, thanks for changing the title.
Re: Why must bitfields sum to a multiple of a byte?
On Tuesday, 31 July 2012 at 15:25:55 UTC, Andrej Mitrovic wrote: On 7/31/12, monarch_dodra wrote: The bug is only when the field is EXACTLY 32 bits BTW. bitfields works quite nice with 33 or whatever. More details in the report. Yeah 32 or 64 bits, thanks for changing the title. I wonder, is it really a bug? If you are going to have it fill a whole size it would fit anyways, why even put it in as a bitfield? You could just declare it separately. I get the feeling it's not so much a bug as a design feature. If you really needed a full size not aligned with whole bytes (or padded appropriately) then I could understand, but still... And I'm the one that changed the title name. Suddenly I'm reminded of south park (movie) and the buttfor.
Re: Why must bitfields sum to a multiple of a byte?
On 7/31/12, Era Scarecrow wrote: > I wonder, is it really a bug? If you are going to have it fill a > whole size it would fit anyways, why even put it in as a > bitfield? You could just declare it separately. I don't really know, I'm looking at this from a point of wrapping C++. I haven't used bitfields myself in my own code.
Re: Why must bitfields sum to a multiple of a byte?
On Tuesday, 31 July 2012 at 16:48:37 UTC, Andrej Mitrovic wrote: On 7/31/12, Era Scarecrow wrote: I wonder, is it really a bug? If you are going to have it fill a whole size it would fit anyways, why even put it in as a bitfield? You could just declare it separately. I don't really know, I'm looking at this from a point of wrapping C++. I haven't used bitfields myself in my own code. I'd say it's not a bug since C/C++ is free to reorder the fields you'd need to tinker with it anyways; HOWEVER if you still need to be able to have it then who's to stop you from doing it? I think more likely a flag/version or some indicator that you didn't make a mistake, such as making them depreciated so it complains to you. Kinda like how you can't make assignments in if statements or do useless compares, it's an error and helps prevent issues that are quite obviously mistakes.
Re: Why must bitfields sum to a multiple of a byte?
On Tuesday, 31 July 2012 at 16:16:00 UTC, Era Scarecrow wrote: On Tuesday, 31 July 2012 at 15:25:55 UTC, Andrej Mitrovic wrote: On 7/31/12, monarch_dodra wrote: The bug is only when the field is EXACTLY 32 bits BTW. bitfields works quite nice with 33 or whatever. More details in the report. Yeah 32 or 64 bits, thanks for changing the title. I wonder, is it really a bug? If you are going to have it fill a whole size it would fit anyways, why even put it in as a bitfield? You could just declare it separately. I get the feeling it's not so much a bug as a design feature. If you really needed a full size not aligned with whole bytes (or padded appropriately) then I could understand, but still... And I'm the one that changed the title name. Suddenly I'm reminded of south park (movie) and the buttfor. No, it's a bug. There is no reason for it to fail (and it certainly isn't a feature). Maybe the user wants to pack an "uint, ushort, ubyte, ubyte" together in a struct, but doesn't want the rest of that struct's members 1-aligned? Maybe the user needs a 32 bit ulong? This way the ulong only takes 32 bits, but can still be implicitly passed to functions expecting ulongs. Maybe the user generated the mixin using another template? For example, testing integers from 10 bits wide to 40 bits wide? Should he write a special case for 32? ... Now I'm not saying it is big bug or anything, but it is something that should be supported... Or at least explicitly asserted until fixed...
Re: Why must bitfields sum to a multiple of a byte?
On Tuesday, 31 July 2012 at 16:59:11 UTC, monarch_dodra wrote: No, it's a bug. There is no reason for it to fail (and it certainly isn't a feature). If I made two fields in a 64bit bitfield, each 32bits int's I'd like it to complain; If it's calculated from something else then finding the problem may be a little more difficult. But that's how my mind works, give you the tools you need to do whatever you want including shooting yourself in the foot (although you need to work harder to do that than C++). Maybe the user wants to pack an "uint, ushort, ubyte, ubyte" together in a struct, but doesn't want the rest of that struct's members 1-aligned? That would be the one reason that makes sense; Course can't you align sections at 1 byte and then by the default afterwards? Course now that I think about it, some systems don't have options to do byte alignments and require to access memory at 4/8 byte alignments. This makes sense needing to support it. Maybe the user needs a 32 bit ulong? This way the ulong only takes 32 bits, but can still be implicitly passed to functions expecting ulongs. I would think the bug only showed itself if you did int at 32bits and ulong at 64 bits, not ulong at 32bits. Maybe the user generated the mixin using another template? For example, testing integers from 10 bits wide to 40 bits wide? Should he write a special case for 32? Ummm. Yeah I think I see what your saying; And you're probably right a special case would be less easily documented (and more a pain) when it shouldn't need a special case. Now I'm not saying it is big bug or anything, but it is something that should be supported... Or at least explicitly asserted until fixed...
Re: Why must bitfields sum to a multiple of a byte?
On 07/31/2012 06:57 PM, Era Scarecrow wrote: On Tuesday, 31 July 2012 at 16:48:37 UTC, Andrej Mitrovic wrote: On 7/31/12, Era Scarecrow wrote: I wonder, is it really a bug? If you are going to have it fill a whole size it would fit anyways, why even put it in as a bitfield? You could just declare it separately. I don't really know, I'm looking at this from a point of wrapping C++. I haven't used bitfields myself in my own code. I'd say it's not a bug since C/C++ is free to reorder the fields you'd need to tinker with it anyways; HOWEVER if you still need to be able to have it then who's to stop you from doing it? I think more likely a flag/version or some indicator that you didn't make a mistake, such as making them depreciated so it complains to you. Kinda like how you can't make assignments in if statements or do useless compares, it's an error and helps prevent issues that are quite obviously mistakes. This is obviously a mistake in the bitfield implementation. What else could be concluded from the error message: std\bitmanip.d(76): Error: shift by 32 is outside the range 0..31 Requesting a 32 bit or 64 bit member on the other hand is not a mistake, and it is not useless, therefore the analogy breaks down. (Also IMO, the once-in-a-year wtf that is caused by accidentally assigning in an if condition does not justify special casing assignment expressions inside if conditions. Also, what is an useless compare?)
Re: Why must bitfields sum to a multiple of a byte?
On Tuesday, 31 July 2012 at 17:17:43 UTC, Timon Gehr wrote: (Also IMO, the once-in-a-year wtf that is caused by accidentally assigning in an if condition does not justify special casing assignment expressions inside if conditions. Also, what is an useless compare?) I've noticed in my experience, DMD gives you an error if you do a statement that has no effect; IE: 1 + 2; //statement has no effect a == b;//ditto
Re: Why must bitfields sum to a multiple of a byte?
On Tuesday, 31 July 2012 at 17:17:25 UTC, Era Scarecrow wrote: On Tuesday, 31 July 2012 at 16:59:11 UTC, monarch_dodra wrote: Maybe the user needs a 32 bit ulong? This way the ulong only takes 32 bits, but can still be implicitly passed to functions expecting ulongs. I would think the bug only showed itself if you did int at 32bits and ulong at 64 bits, not ulong at 32bits. No, the bug shows itself if the first field is 32 bits, regardless of (ulong included). I would add though that requesting a field in bits that is bigger than the type of the field should not work (IMO). EG: struct A { mixin(bitfields!( ushort, "a", 24, uint,"", 8 ) ); } I don't see any way how that could make sense... But it *is* legal in C and C++... But it does generates warnings... I think it should static assert in D. On Tuesday, 31 July 2012 at 17:21:00 UTC, Era Scarecrow wrote: On Tuesday, 31 July 2012 at 17:17:43 UTC, Timon Gehr wrote: (Also IMO, the once-in-a-year wtf that is caused by accidentally assigning in an if condition does not justify special casing assignment expressions inside if conditions. Also, what is an useless compare?) I've noticed in my experience, DMD gives you an error if you do a statement that has no effect; IE: 1 + 2; //statement has no effect a == b;//ditto That's part of the standard: Statements that have no effect are illegal. This is a good think, IMO. I've seen MANY C++ bugs that could have been saved by that. Regarding the assignment in if. I think it is a good thing. D sides with safety. If you *really* want to test assign, you can always comma operator it. void main() { int a = 0, b = 5; while(a = --b, a) //YES, I *DO* want to assign! { write(a); } }; I'm sure the compiler will optimize away what it needs.
Re: Why must bitfields sum to a multiple of a byte?
On Tuesday, 31 July 2012 at 17:34:33 UTC, monarch_dodra wrote: No, the bug shows itself if the first field is 32 bits, regardless of (ulong included). I would add though that requesting a field in bits that is bigger than the type of the field should not work (IMO). EG: struct A { mixin(bitfields!( ushort, "a", 24, uint,"", 8 ) ); } I don't see any way how that could make sense... But it *is* legal in C and C++... But it does generates warnings... Maybe so ushort has extra padding for expansion at some later date when they change it to uint?? could put an assert in, but if it doesn't break code... I think it should static assert in D. Glancing over the issue, the [0..31] is a compiler error based on bit shifting (not bitfields itself); if the storage type is ulong then it shouldn't matter if the first one is a 32bit size or not. Unless... Nah, couldn't be... I'll look it over later to be sure. That's part of the standard: Statements that have no effect are illegal. This is a good think, IMO. I've seen MANY C++ bugs that could have been saved by that. Regarding the assignment in if. I think it is a good thing. D sides with safety. If you *really* want to test assign, you can always comma operator it.
Re: Why must bitfields sum to a multiple of a byte?
On Tuesday, 31 July 2012 at 17:17:43 UTC, Timon Gehr wrote: This is obviously a mistake in the bitfield implementation. What else could be concluded from the error message: std\bitmanip.d(76): Error: shift by 32 is outside the range 0..31 Requesting a 32 bit or 64 bit member on the other hand is not a mistake, and it is not useless, therefore the analogy breaks down. Well curiously it was easier to fix than I thought (a line for a static if, and a modification of the masking)... Was there any other bugs that come to mind? Anything of consequence?
fixing the bitfields implimentation
On Tuesday, 31 July 2012 at 17:17:43 UTC, Timon Gehr wrote: This is obviously a mistake in the bitfield implementation. What else could be concluded from the error message: std\bitmanip.d(76): Error: shift by 32 is outside the range 0..31 Requesting a 32 bit or 64 bit member on the other hand is not a mistake, and it is not useless, therefore the analogy breaks down. Well curiously it was easier to fix than I thought (a line for a static if, and a modification of the masking)... Was there any other bugs that come to mind? Anything of consequence?
Re: Top level array constness discarding and Variant
On Monday, 30 July 2012 at 20:56:30 UTC, Jonathan M Davis wrote: On Monday, July 30, 2012 23:44:56 cybevnm wrote: During initializing Variant, D discards top level const of array, which leads to little unintuitive behaviour. Consider code: import std.stdio; import std.variant; void main() { const int[] arr; Variant v = Variant( arr ); writeln( v.peek!( typeof( arr ) )() ); writeln( v.peek!( const(int)[] )() ); writeln( v.type() ); } ...and output: %dmd main.d && ./main.d null 7FFF358AE298 const(int)[] As you can see peek works successfully not for original array type, but for type without top level const. Is Variant supposed to work in that way ? Probably not. When arrays are passed to templated functions, they're passed as tail-const (so the constness on the array itself - but not its elements - is stripped), which in general is _way_ more useful than passing them as fully const. However, Variant predates that behavior by quite a while, and it's well-passed due for having extensive work done on its implementation (it's API should be fine, but it was implemented when D was much younger, and we can do a much better job of it now). There's a discussion on that in the main newsgroup at the moment actually. In any case, please create a bug report for this: http://d.puremagic.com/issues - Jonathan M Davis http://d.puremagic.com/issues/show_bug.cgi?id=8486
Re: Why must bitfields sum to a multiple of a byte?
On 07/31/2012 09:15 AM, Era Scarecrow wrote: > On Tuesday, 31 July 2012 at 15:25:55 UTC, Andrej Mitrovic wrote: >> On 7/31/12, monarch_dodra wrote: >>> The bug is only when the field is EXACTLY 32 bits BTW. bitfields >>> works quite nice with 33 or whatever. More details in the report. >> >> Yeah 32 or 64 bits, thanks for changing the title. > > I wonder, is it really a bug? If you are going to have it fill a whole > size it would fit anyways, why even put it in as a bitfield? You could > just declare it separately. It can happen in templated code where the width of the first field may be a template parameter. I wouldn't want to 'static if (width == 32)'. But thanks for fixing the bug already! :) Ali
Re: Implementing a Monitor
Thank you for your reply. I have some more questions: I simplified my example. Now my monitor is used for mutual exclusion, to understand how monitors work first. // 3 threads are running P() - the main thread is not one of them void P() { while( run ) { monitor.EnterCritical2(); // critical section writeln(count); monitor.ExitCritical2(); } } class Monitor { Mutex mutex; Cond cond; bool in_use = false; this() { mutex = new Mutex(); cond = new Cond(mutex); } void EnterCritical() { // The synchronized statement is required to ensure only one thread will be able // to access the block synchronized(mutex) { while( in_use ) cwait(cond); in_use = true; ++count; } } void ExitCritical() { synchronized(mutex) { --count; in_use = false; cnotify(cond); } } } 1) In class (in college), I have learned that monitors "by nature" grant access only to one thread in their functions. That's what synchronized(mutex) is used for right? 2) Why synchronized(mutex) and not synchronized(this) (I know this is not good practise, but is there something more?) or not synchronized(some else object)? 3) You correctly changed my "EnterCritical()" code to "While" instead of "if", because, and please correct me if I'm wrong, we are using notify() and not signal(). 4) I wrote my own version of signal. It's: void csignal(Condition cond) { cond.notify(); Thread.yield(); } The logic is that it notifies another Thread and then forces a context switch, so it's like calling signal(). Is it correct? I changed my EnterCritical() to use "if" instead of "while" because I use my own version of signal() in ExitCritical(). void EnterCritical2() { synchronized(mutex) { if( in_use ) cwait(cond); in_use = true; ++count; } } void ExitCritical2() { synchronized(mutex) { --count; in_use = false; csignal(cond); } } However, when "count" is printed in P(), its value is 3 (it was 1 before which it ensured that mutual exclusion was correct). If I change the "if" to "while" it works, but that's not the purpose of signal(). I'm pretty sure that when using "signal" it's "if", not "while". What am I doing wrong? 5) Are the threads running concurrently on one core or in parallel (provided that the PC has more than one cores). Mine has 2 cores x 2 threads each. Thank you. PS: I'm writing some small programs that demonstrate concurrency in D. The reason is I suggested it to my university professor as a way to learn about this stuff in a practical manner. So I guess if he likes them, D will be tought in a university :)
Re: Why must bitfields sum to a multiple of a byte?
On 31-Jul-12 22:21, Era Scarecrow wrote: On Tuesday, 31 July 2012 at 17:17:43 UTC, Timon Gehr wrote: This is obviously a mistake in the bitfield implementation. What else could be concluded from the error message: std\bitmanip.d(76): Error: shift by 32 is outside the range 0..31 Requesting a 32 bit or 64 bit member on the other hand is not a mistake, and it is not useless, therefore the analogy breaks down. Well curiously it was easier to fix than I thought (a line for a static if, and a modification of the masking)... Was there any other bugs that come to mind? Anything of consequence? Great to see things moving. Could you please do a separate pull for bitfields it should get merged easier and it seems like a small but important bugfix. -- Dmitry Olshansky
Re: sorting failed error
On Tuesday, 31 July 2012 at 09:41:31 UTC, maarten van damme wrote: I now tried to bring it to the next level, using concurrency to bread a couple of populations and make the best solutions migrate between them. But, to use concurrency in D, one has to continually cast between immutable, cast immutable away, Not only that, casting away from immutable (or too, the error message is not informative at all) you get error's along the line of "opEquals doesn't work with immutable arguments"... Why is it that cumbersome? It seems like D took a good idea and ruined it with all that const-stuff. I have the feeling that I've completely missed the whole idea on how concurrency in D should work. Is it normal that you have to either mess with immutable or with the broken shared? Am I implementing everything wrong? Use std.parallelism. It has everything that (I think) you need, e.g. support for parallel for, tasks and more.
Re: Why must bitfields sum to a multiple of a byte?
On Tuesday, 31 July 2012 at 20:41:55 UTC, Dmitry Olshansky wrote: On 31-Jul-12 22:21, Era Scarecrow wrote: Well curiously it was easier to fix than I thought (a line for a static if, and a modification of the masking)... Was there any other bugs that come to mind? Anything of consequence? Great to see things moving. Could you please do a separate pull for bitfields it should get merged easier and it seems like a small but important bugfix. Guess this means I'll be working on BitArrays a bit later and work instead on the bitfields code. What fun... :) I thought I had bitfields as separate already, but it's kinda thrown both sets of changes in. Once I figure it out I'll get them separated and finish work on the bitfields.