digitalmars.D - Why isn't bool allowed as AA key type?
- David Nadlinger (8/8) May 28 2011 Hello all,
- KennyTM~ (7/16) May 28 2011 The limitation is apparently introduced in 0.68* (!), but the changelog
- Nick Sabalausky (4/12) May 29 2011 It works for me. I use it all the time as a hash set. What version are y...
- Daniel Gibson (5/24) May 29 2011 void main() {
- David Nadlinger (10/17) May 29 2011 Are you sure you are using bool _keys_, not values? On a related note,
- Nick Sabalausky (3/16) May 29 2011 Shit, you're right. Not thinking here...
- Steven Schveighoffer (9/27) Jun 01 2011 There is always dcollections (has both Hash- and TreeSet). It is boost ...
- Timon Gehr (5/12) Jun 02 2011 Well, how? Since an 'in' expression returns an internal pointer into the...
- Steven Schveighoffer (7/23) Jun 02 2011 What is the issue here? Are you saying you can use the pointer after
- Timon Gehr (16/40) Jun 02 2011 Huh?
- Steven Schveighoffer (17/66) Jun 02 2011 That is not a removal:
- Timon Gehr (36/63) Jun 02 2011 So, destroying the container does not free it's elements, but removing o...
Hello all, is there a reason bool isn't allowed as key type for associative arrays (mtype.c:3995)? The docs don't mention this. bool-key AAs probably wouldn't be too useful in practice, but it seems like a quite arbitrary and unexpected limitation to me – e.g. I would have to add special cases to all my Thrift map handling code. In case this is not on purpose, I'd be happy to put together a pull request. David
May 28 2011
On May 29, 11 01:54, David Nadlinger wrote:Hello all, is there a reason bool isn't allowed as key type for associative arrays (mtype.c:3995)? The docs don't mention this. bool-key AAs probably wouldn't be too useful in practice, but it seems like a quite arbitrary and unexpected limitation to me – e.g. I would have to add special cases to all my Thrift map handling code. In case this is not on purpose, I'd be happy to put together a pull request. DavidThe limitation is apparently introduced in 0.68* (!), but the changelog doesn't show why this is added either. Perhaps it was because at that time the type was known as 'bit'. If that's the case, I believe such limitation is no longer applicable. *: https://github.com/D-Programming-Language/dmd/commit/42b868c31085211cbb8838325b72d7522f9164d2#L6R1544
May 28 2011
"David Nadlinger" <see klickverbot.at> wrote in message news:irrd5h$hdj$1 digitalmars.com...Hello all, is there a reason bool isn't allowed as key type for associative arrays (mtype.c:3995)? The docs don't mention this. bool-key AAs probably wouldn't be too useful in practice, but it seems like a quite arbitrary and unexpected limitation to me - e.g. I would have to add special cases to all my Thrift map handling code. In case this is not on purpose, I'd be happy to put together a pull request.It works for me. I use it all the time as a hash set. What version are you on? I've been using D2, maybe it's a D1 issue? If so, I'd file a bug report.
May 29 2011
Am 29.05.2011 22:21, schrieb Nick Sabalausky:"David Nadlinger" <see klickverbot.at> wrote in message news:irrd5h$hdj$1 digitalmars.com...void main() { string[bool] map; } test.d(2): Error: can't have associative array key of boolHello all, is there a reason bool isn't allowed as key type for associative arrays (mtype.c:3995)? The docs don't mention this. bool-key AAs probably wouldn't be too useful in practice, but it seems like a quite arbitrary and unexpected limitation to me - e.g. I would have to add special cases to all my Thrift map handling code. In case this is not on purpose, I'd be happy to put together a pull request.It works for me. I use it all the time as a hash set. What version are you on? I've been using D2, maybe it's a D1 issue? If so, I'd file a bug report.
May 29 2011
On 5/29/11 10:21 PM, Nick Sabalausky wrote:"David Nadlinger"<see klickverbot.at> wrote in message news:irrd5h$hdj$1 digitalmars.com...Are you sure you are using bool _keys_, not values? On a related note, https://github.com/D-Programming-Language/dmd/pull/77 seems to be all required for making them work. By the way, do you happen to have a complete hash set implementation lying around? I'd be interested in preparing and proposing one for std.container, as I need one for Thrift (currently, I have a really, REALLY preliminary and buggy one based on a void[0] AA, see https://github.com/klickverbot/thrift/blob/d-gsoc/lib/d/src/thrift/hashset.d). David[…] is there a reason bool isn't allowed as key type for associative arrays (mtype.c:3995)? The docs don't mention this. […]It works for me. I use it all the time as a hash set. What version are you on? I've been using D2, maybe it's a D1 issue? If so, I'd file a bug report.
May 29 2011
"David Nadlinger" <see klickverbot.at> wrote in message news:irubao$gpu$1 digitalmars.com...On 5/29/11 10:21 PM, Nick Sabalausky wrote:Shit, you're right. Not thinking here..."David Nadlinger"<see klickverbot.at> wrote in message news:irrd5h$hdj$1 digitalmars.com...Are you sure you are using bool _keys_, not values? On a related note, https://github.com/D-Programming-Language/dmd/pull/77 seems to be all required for making them work.[.] is there a reason bool isn't allowed as key type for associative arrays (mtype.c:3995)? The docs don't mention this. [.]It works for me. I use it all the time as a hash set. What version are you on? I've been using D2, maybe it's a D1 issue? If so, I'd file a bug report.
May 29 2011
On Sun, 29 May 2011 16:41:56 -0400, David Nadlinger <see klickverbot.at> wrote:On 5/29/11 10:21 PM, Nick Sabalausky wrote:There is always dcollections (has both Hash- and TreeSet). It is boost 1.0, so feel free to steal anything to propose for std.container (in fact, RedBlackTree is from dcollections). Note that I'm nowhere near an expert on hashing, so I'm not sure how it will perform against AAs. I know it does beat them using my custom allocator, but that's not a truly fair comparison -- AA's could be written with a custom allocator too. -Steve"David Nadlinger"<see klickverbot.at> wrote in message news:irrd5h$hdj$1 digitalmars.com...Are you sure you are using bool _keys_, not values? On a related note, https://github.com/D-Programming-Language/dmd/pull/77 seems to be all required for making them work. By the way, do you happen to have a complete hash set implementation lying around? I'd be interested in preparing and proposing one for std.container, as I need one for Thrift (currently, I have a really, REALLY preliminary and buggy one based on a void[0] AA, see https://github.com/klickverbot/thrift/blob/d-gsoc/lib/d/src/thrift/hashset.d).[…] is there a reason bool isn't allowed as key type for associative arrays (mtype.c:3995)? The docs don't mention this. […]It works for me. I use it all the time as a hash set. What version are you on? I've been using D2, maybe it's a D1 issue? If so, I'd file a bug report.
Jun 01 2011
Steven Schveighoffer wrote:There is always dcollections (has both Hash- and TreeSet). It is boost 1.0, so feel free to steal anything to propose for std.container (in fact, RedBlackTree is from dcollections). Note that I'm nowhere near an expert on hashing, so I'm not sure how it will perform against AAs. I know it does beat them using my custom allocator, but that's not a truly fair comparison -- AA's could be written with a custom allocator too. -SteveWell, how? Since an 'in' expression returns an internal pointer into the AA for value types, they cannot do better than to rely on GC. This rules out heavy AA use for real-time applications. I think AAs are broken. Timon
Jun 02 2011
On Thu, 02 Jun 2011 06:21:28 -0400, Timon Gehr <timon.gehr gmx.ch> wrote:Steven Schveighoffer wrote:What is the issue here? Are you saying you can use the pointer after destroying the element, because you can't. AA's free an element when it is removed. BTW, dcollections' custom allocator does use the GC, it just uses it in bulk instead of allocating for each node. -SteveThere is always dcollections (has both Hash- and TreeSet). It is boost 1.0, so feel free to steal anything to propose for std.container (in fact, RedBlackTree is from dcollections). Note that I'm nowhere near an expert on hashing, so I'm not sure how it will perform against AAs. I know it does beat them using my custom allocator, but that's not a truly fair comparison -- AA's could be written with a custom allocator too. -SteveWell, how? Since an 'in' expression returns an internal pointer into the AA for value types, they cannot do better than to rely on GC. This rules out heavy AA use for real-time applications. I think AAs are broken.
Jun 02 2011
On Thu, 02 Jun 2011 06:21:28 -0400, Timon Gehr <timon.gehr gmx.ch> wrote:Huh? import std.stdio,core.memory; int* test(){ int[int] aa=[0:0,1:1,2:2,3:3,4:4,5:5]; return 1 in aa; } void main(){ int* u=test(); GC.collect(); assert(*u==1); /*use u for fun and profit*/ }Steven Schveighoffer wrote:What is the issue here? Are you saying you can use the pointer after destroying the element, because you can't. AA's free an element when it is removed.There is always dcollections (has both Hash- and TreeSet). It is boost 1.0, so feel free to steal anything to propose for std.container (in fact, RedBlackTree is from dcollections). Note that I'm nowhere near an expert on hashing, so I'm not sure how it will perform against AAs. I know it does beat them using my custom allocator, but that's not a truly fair comparison -- AA's could be written with a custom allocator too. -SteveWell, how? Since an 'in' expression returns an internal pointer into the AA for value types, they cannot do better than to rely on GC. This rules out heavy AA use for real-time applications. I think AAs are broken.BTW, dcollections' custom allocator does use the GC, it just uses it in bulk instead of allocating for each node. -SteveIf AAs would do that, the whole bulk could be pinned by one pointer to one element inside it, which is still not optimal. Returning internal pointers into a data structure is always a bad idea (assuming it must be safe). Timon
Jun 02 2011
On Thu, 02 Jun 2011 06:44:33 -0400, Timon Gehr <timon.gehr gmx.ch> wrote:That is not a removal: int[int] aa=[0:0,1:1,2:2,3:3,4:4,5:5]; auto ret = 1 in aa; aa.remove(1); return ret; // ret now points to free'd memory Your equivalent code using dcollections' custom allocator would work too, the GC backs up the custom allocator.On Thu, 02 Jun 2011 06:21:28 -0400, Timon Gehr <timon.gehr gmx.ch> wrote:Huh? import std.stdio,core.memory; int* test(){ int[int] aa=[0:0,1:1,2:2,3:3,4:4,5:5]; return 1 in aa; } void main(){ int* u=test(); GC.collect(); assert(*u==1); /*use u for fun and profit*/ }Steven Schveighoffer wrote:What is the issue here? Are you saying you can use the pointer after destroying the element, because you can't. AA's free an element when it is removed.There is always dcollections (has both Hash- and TreeSet). It is boost 1.0, so feel free to steal anything to propose for std.container (in fact, RedBlackTree is from dcollections). Note that I'm nowhere near an expert on hashing, so I'm not sure how it will perform against AAs. I know it does beat them using my custom allocator, but that's not a truly fair comparison -- AA's could be written with a custom allocator too. -SteveWell, how? Since an 'in' expression returns an internal pointer into the AA for value types, they cannot do better than to rely on GC. This rules out heavy AA use for real-time applications. I think AAs are broken.No, but this is a compromise -- better performance vs. smaller footprint. It would be nice if the GC just performed better.BTW, dcollections' custom allocator does use the GC, it just uses it in bulk instead of allocating for each node. -SteveIf AAs would do that, the whole bulk could be pinned by one pointer to one element inside it, which is still not optimal.Returning internal pointers into a data structure is always a bad idea (assuming it must be safe).Then ranges on a container are not possible (a range contains a pointer to the next element). Ranges can be invalidated using a "modification" count, but this removes some valid uses, and it also costs quite a bit (extra int to store range's copy of count, extra check on every range function to ensure counts are synchronized, possible extra pointer to store in range to point at owner container). -Steve
Jun 02 2011
Steven Schveighoffer wrote:That is not a removal:So, destroying the container does not free it's elements, but removing one element does free it?int[int] aa=[0:0,1:1,2:2,3:3,4:4,5:5]; auto ret = 1 in aa; aa.remove(1); return ret; // ret now points to free'd memoryWeeh! It's a dangling pointer built right into the language =)! Is the memory really free'd? Because: import std.stdio,core.memory; int *test(){ int[int] aa=[0:0,1:1,2:2,3:3,4:4,5:5]; int* ret=1 in aa; aa.remove(1);//int* tmp=ret;clear(tmp);//replace line with this to get segfault in main return ret; } void main(){ int *u=test(); assert(*u==1); } I do not get what is happening here, can you help?Your equivalent code using dcollections' custom allocator would work too, the GC backs up the custom allocator.That implies that dcollections' hash map performs poorly in real-time constrained environments too, right?I agree. But GC runtime has to be at least linear in number of alive and garbage objects. It is inherently quite slow.No, but this is a compromise -- better performance vs. smaller footprint. It would be nice if the GC just performed better.BTW, dcollections' custom allocator does use the GC, it just uses it in bulk instead of allocating for each node. -SteveIf AAs would do that, the whole bulk could be pinned by one pointer to one element inside it, which is still not optimal.Well, it is possible unless you want to represent those ranges as pairs of raw pointers. Raw pointers have not enough type information to be useful as range representation. Even if your ranges can get invalidated, I would not pick a raw pointer as representation. C++ iterators do not leak any pointers to the internal representation of the data structure to the user afaik. &a[123] does on a std::vector, but Ds operator overloading explicitly allows to prevent this. Therefore there _must_ be some merit to the idea. Aren't 'in' expressions returning pointers just a hack to prevent multiple lookups of the same data? I do not think this optimization is worth all the GC overhead (and dangling pointer issues?). TimonReturning internal pointers into a data structure is always a bad idea (assuming it must be safe).Then ranges on a container are not possible (a range contains a pointer to the next element). Ranges can be invalidated using a "modification" count, but this removes some valid uses, and it also costs quite a bit (extra int to store range's copy of count, extra check on every range function to ensure counts are synchronized, possible extra pointer to store in range to point at owner container). -Steve
Jun 02 2011