https://forum.dlang.org/post/mailman.1072.1581112984.31109.digitalmars-d-learn@puremagic.com

On Friday, 7 February 2020 at 22:03:00 UTC, H. S. Teoh wrote:
> On Fri, Feb 07, 2020 at 07:37:08PM +0000, mark via Digitalmars-d-learn wrote:
>> [...]
>
> bool[E] works just fine.
>
> The bool does take up 1 byte, though, so if you're *really* want to optimize that away, you could do this:
>
> 	alias Unit = void[0];
> 	enum unit = Unit.init;
>
> 	// Look, ma! A bona fide set!
> 	Unit[E] mySet;
>
> 	mySet[...] = unit;
> 	mySet.remove(...);
> 	... // etc.
>
> Or you can wrap void[0][E] in a nice user-defined type that gives nice set-like syntax.  But IMO, this is all overkill, and adds needless complexity. Just use bool[E] or std.container.rbtree. :-D
>
>
> T

Can you please explain what does `bool[E]` mean? And how does the code with aliasing void[0] and then using enum even work?

On Tue, Feb 08, 2022 at 09:08:47PM +0000, tastyminerals via Digitalmars-d-learn wrote: [...]
> > bool[E] works just fine.
> > 
> > The bool does take up 1 byte, though, so if you're *really* want to optimize that away, you could do this:
> > 
> > 	alias Unit = void[0];
> > 	enum unit = Unit.init;
> > 
> > 	// Look, ma! A bona fide set!
> > 	Unit[E] mySet;
> > 
> > 	mySet[...] = unit;
> > 	mySet.remove(...);
> > 	... // etc.
> > 
> > Or you can wrap void[0][E] in a nice user-defined type that gives nice set-like syntax.  But IMO, this is all overkill, and adds needless complexity. Just use bool[E] or std.container.rbtree. :-D
[...]
> Can you please explain what does `bool[E]` mean?

E is whatever key type you want to use. String, or integer ID, or whatever you want to put in your set.


> And how does the code with aliasing void[0] and then using enum even work?

The alias is a workaround for a syntactic limitation in D, because you cannot write `mySet[someKey] = void[0].init;` without a syntax error. So we use the alias to give `void[0]` a name that we can refer to in assignment statements, so that we can assign its values to the AA.

As for `void[0]` itself, it's just a zero-element static array of an indeterminate type. The whole point is to create something that occupies 0 bytes. The actual type doesn't actually matter; you could have used int[0] and it'd work too.  (You can't use an empty struct because empty structs have size 1.)  By using a zero-sized value type for the AA, we effectively turn it into a set: it only stores keys.  Well, technically it stores values of zero size too, but since it's zero-sized, it's as if the value isn't there, and it incurs zero memory overhead. (Whereas an empty struct would likely occupy an entire machine word, rounded up from size 1.)

But as I said, this is overkill for something so trivial. Using `bool[E]` or an RBTree works just fine.


T

-- 
Javascript is what you use to allow third party programs you don't know anything about and doing you know not what to run on your computer. -- Charles Hixson

On Tue, Feb 08, 2022 at 09:47:13PM +0000, Paul Backus via Digitalmars-d-learn wrote: [...]
> The `alias` and the `enum` just make the code a little nicer to read by letting you write `Unit` instead of `void[0]` and `unit` instead of `void[0].init`. You could get rid of them and the code would work exactly the same way; it'd just be a little bit uglier:
> 
>     void[0][E] mySet;
> 
>     mySet[...] = void[0].init;
[...]

Unfortunately, this doesn't work due to a syntax restriction (the parser isn't expecting a type name after the `=`, and will raise a syntax error). So the alias is in fact necessary.


T

-- 
Fact is stranger than fiction.

On Tuesday, 8 February 2022 at 21:58:49 UTC, H. S. Teoh wrote:
> On Tue, Feb 08, 2022 at 09:47:13PM +0000, Paul Backus via Digitalmars-d-learn wrote: [...]
>> The `alias` and the `enum` just make the code a little nicer to read by letting you write `Unit` instead of `void[0]` and `unit` instead of `void[0].init`. You could get rid of them and the code would work exactly the same way; it'd just be a little bit uglier:
>> 
>>     void[0][E] mySet;
>> 
>>     mySet[...] = void[0].init;
> [...]
>
> Unfortunately, this doesn't work due to a syntax restriction (the parser isn't expecting a type name after the `=`, and will raise a syntax error). So the alias is in fact necessary.

Ah, yeah, I forgot about that bug.

It also works if you use parentheses:

    mySet[...] = (void[0]).init;

On Tue, Feb 08, 2022 at 10:02:30PM +0000, Paul Backus via Digitalmars-d-learn wrote: [...]
> It also works if you use parentheses:
> 
>     mySet[...] = (void[0]).init;

OT1H, nice that works! ... but OTOH, ugh, it looks so ugly. :-P  I think I'll just stick with the alias.


T

-- 
Who told you to swim in Crocodile Lake without life insurance??

On Thu, Feb 10, 2022 at 12:53:08AM +0000, Siarhei Siamashka via Digitalmars-d-learn wrote:
> On Wednesday, 9 February 2022 at 21:05:47 UTC, Siarhei Siamashka wrote:
> > Is the current implementation of associative arrays in D language resistant to Denial of Service hash collision attacks?
> 
> Answering to myself. No, it isn't. Here's a simple example:
[...]
> ulong[] generate_bad_array(ulong n)
> {
>     return iota(n).map!(x => (x << 46)).array;
> }
[...]
> == adversarially constructed array ==
> n=100000, unique_elements=100000, assoc time: 22626 ms, rbtree time: 15 ms
> ```

Nice investigation!  This should be filed as a bug.

I remember browsing through various hash functions in druntime before (built-in AA's use per-type hash functions), and many of them were trivial, which would imply that it's trivial to construct adversarial input that triggers a large number of collisions for various basic types.


T

-- 
Give me some fresh salted fish, please.

On Tuesday, 8 February 2022 at 21:42:06 UTC, H. S. Teoh wrote:
> On Tue, Feb 08, 2022 at 09:08:47PM +0000, tastyminerals via Digitalmars-d-learn wrote: [...]
>> > [...]
> [...]
>> [...]
>
> E is whatever key type you want to use. String, or integer ID, or whatever you want to put in your set.
>
> [...]

Thank you! That's neat.