Re: Filling an array at compile time
On Wednesday, 9 February 2022 at 16:37:22 UTC, Ali Çehreli wrote: On 2/9/22 01:07, bauss wrote: > It will not run at compile-time because csvText is a runtime variable. > It should be enum to be accessible at compile-time. Yes. For the sake of completeness, any expression needed at compile time will be (attempted to be) executed at compile time. For example, an expression used as a template parameter will be executed at compile time as well. > The append operation > will be executed at runtime, which means that even if the loop runs at > compile-time then you're effectively not winning anything and it > basically just becomes a loop-unroll manually done. That's not true. It all depends on how the expression is needed. If for example, the variable were defined as enum, the compiler had to execute the code at compile time to compute its value. > The solution would be to create a function that returns a string [...] > And then simply using mixin That is unnecessary and hurts readability. :/ Most programmers see string mixins as a last resort. In any case, some people may find a compile-time file parsing example that I included in a presentation: https://youtu.be/dRORNQIB2wA?t=3157 Ali Thank you Ali for the clarifications
Re: how to handle very large array?
On Thursday, 10 February 2022 at 01:43:54 UTC, H. S. Teoh wrote: On Thu, Feb 10, 2022 at 01:32:00AM +, MichaelBi via Digitalmars-d-learn wrote: On Wednesday, 9 February 2022 at 19:48:49 UTC, H. S. Teoh wrote: > [...] thanks, very helpful! i am using a assocArray now... Are you sure that's what you need? T https://youtu.be/yJjpXJm7x0o?t=213
Re: how to handle very large array?
On Thu, Feb 10, 2022 at 01:32:00AM +, MichaelBi via Digitalmars-d-learn wrote: > On Wednesday, 9 February 2022 at 19:48:49 UTC, H. S. Teoh wrote: > > [...] > > thanks, very helpful! i am using a assocArray now... Are you sure that's what you need? T -- Computers are like a jungle: they have monitor lizards, rams, mice, c-moss, binary trees... and bugs.
Re: how to handle very large array?
On Wednesday, 9 February 2022 at 19:48:49 UTC, H. S. Teoh wrote: [...] thanks, very helpful! i am using a assocArray now...
Re: How to use sets in D?
On Thu, Feb 10, 2022 at 12:53:08AM +, 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=10, unique_elements=10, 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.
Re: How to use sets in D?
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:
```D
import std, core.time;
const ulong n = 10;
// Count the number of unique elements using associative array
ulong count_unique_values_assoc(const ulong[] a)
{
bool[ulong] set;
foreach (x ; a)
set[x] = true;
return set.length;
}
// Count the number of unique elements using redBlackTree
ulong count_unique_values_rbtree(const ulong[] a)
{
auto set = redBlackTree!("a (x << 46)).array;
}
// Benchmark associative array vs. rbtree
void run_benchmark(ulong[] a)
{
auto t1 = MonoTime.currTime;
auto result_assoc = a.count_unique_values_assoc;
auto t2 = MonoTime.currTime;
auto result_rbtree = a.count_unique_values_rbtree;
auto t3 = MonoTime.currTime;
assert(result_assoc == result_rbtree);
writefln("n=%d, unique_elements=%d, assoc time: %d ms, rbtree
time: %d ms",
a.length, result_assoc,
(t2 - t1).total!"msecs",
(t3 - t2).total!"msecs");
}
void main()
{
assert([1UL, 1UL, 2UL].count_unique_values_assoc == 2);
assert([1UL, 1UL, 2UL].count_unique_values_rbtree == 2);
writefln("== consecutive numbers ==");
n.iota.array.run_benchmark;
writefln("\n== random numbers between 0 and 99 ==");
n.iota.map!(_ => uniform(0UL, 100UL)).array.run_benchmark;
writefln("\n== adversarially constructed array ==");
n.generate_bad_array.run_benchmark;
}
```
Benchmark results using a 64-bit LDC compiler:
```
== consecutive numbers ==
n=10, unique_elements=10, assoc time: 11 ms, rbtree time:
20 ms
== random numbers between 0 and 99 ==
n=10, unique_elements=100, assoc time: 2 ms, rbtree time: 4 ms
== adversarially constructed array ==
n=10, unique_elements=10, assoc time: 22626 ms, rbtree
time: 15 ms
```
Re: How to use sets in D?
On Tuesday, 8 February 2022 at 21:42:06 UTC, H. S. Teoh wrote: But as I said, this is overkill for something so trivial. Using `bool[E]` or an RBTree works just fine. Is the current implementation of associative arrays in D language resistant to Denial of Service hash collision attacks? * https://github.com/dlang/dmd/blob/master/src/dmd/root/aav.d * https://arstechnica.com/information-technology/2011/12/huge-portions-of-web-vulnerable-to-hashing-denial-of-service-attack/ * https://lwn.net/Articles/474912/ * https://codeforces.com/blog/entry/62393 If not, then redBlackTree may be safer to use when dealing with potentially adversarially constructed input data.
Re: how to handle very large array?
On Wed, Feb 09, 2022 at 11:05:23AM -0800, Ali Çehreli via Digitalmars-d-learn wrote: > On 2/9/22 10:38, MoonlightSentinel wrote: > > > There's a way to use a much smaller array to manage the lanternfish > > population... > > As soon as I read your comment, I was reminded of a certain ingenious > sorting algorithm that is O(N). ;) After reading the problem > description, I see your hint was useful. [...] If you know beforehand that your data is discrete and bounded, you can achieve O(N) sort complexity (as opposed to O(N log N), which is the lower bound if you cannot make any assumptions about your data beyond their ordering). You can use pigeonhole sort, for example, i.e., create an M-element array of counters where M is the number of distinct values your elements may have, then just iterate over your data and increment the counter corresponding to each element you find (using array indexing for O(1) access to each counter). Then iterate over the array of counters in order and replace the input data with that many copies of each element. Your overall complexity then would be O(N+M), which would be O(N) if M is about the same order of magnitude as N or less. However, this algorithm quickly becomes impractical when M grows large, because you will soon need to create many more slots than there are input elements. For example, sorting a general int[] this way would require 2^32 counters, which is usually overkill unless your input has close to 2^32 elements. (You could do it if you knew your int's are ≤ M for some small value of M, though. But it won't work for general int[] that can contain any value.) And trying to sort a general ulong[] this way will not work because you would need an array of 2^64 counters, which would not only exhaust all available RAM in today's computers, but also take a ridiculously long amount of time to iterate in the second step. The insight here is *taking advantage of additional structure in your data*. If you take the general, minimal-assumptions approach, the best you can do is the general O(N log N) algorithm. However, by exploiting additional structure in your data, you can do better. Similarly, if you take the naïve approach to modelling your lanternfish, you'll end up with an unwieldy array that's far too large to fit in RAM. If you exploit the additional structure in your data, however, you can accomplish the same task with a much smaller array. T -- Latin's a dead language, as dead as can be; it killed off all the Romans, and now it's killing me! -- Schoolboy
Re: how to handle very large array?
On 2/9/22 10:38, MoonlightSentinel wrote: > There's a way to use a much smaller array to manage the lanternfish > population... As soon as I read your comment, I was reminded of a certain ingenious sorting algorithm that is O(N). ;) After reading the problem description, I see your hint was useful. Ali
Re: how to handle very large array?
On Wednesday, 9 February 2022 at 10:03:21 UTC, MichaelBi wrote: day6 of the advent of code 2021 needs to handle an array of 10^12 length, or even bigger... As others have mentioned, huge arrays require appropriate memory / the use of memory-mapped files to actually store it. But the calculation will take a *long* time even if your program could allocate an array of that size. There's a way to use a much smaller array to manage the lanternfish population...
Re: Filling an array at compile time
On 2/9/22 08:37, Ali Çehreli wrote: > In any case, some people may find a compile-time file parsing example > that I included in a presentation: That should mean "may find interesting". And I've just realized that the chapter link is off in that video. This is the beginning of that section: https://www.youtube.com/watch?v=dRORNQIB2wA=3065s Ali
Re: Filling an array at compile time
On 2/9/22 01:07, bauss wrote: > It will not run at compile-time because csvText is a runtime variable. > It should be enum to be accessible at compile-time. Yes. For the sake of completeness, any expression needed at compile time will be (attempted to be) executed at compile time. For example, an expression used as a template parameter will be executed at compile time as well. > The append operation > will be executed at runtime, which means that even if the loop runs at > compile-time then you're effectively not winning anything and it > basically just becomes a loop-unroll manually done. That's not true. It all depends on how the expression is needed. If for example, the variable were defined as enum, the compiler had to execute the code at compile time to compute its value. > The solution would be to create a function that returns a string [...] > And then simply using mixin That is unnecessary and hurts readability. :/ Most programmers see string mixins as a last resort. In any case, some people may find a compile-time file parsing example that I included in a presentation: https://youtu.be/dRORNQIB2wA?t=3157 Ali
Re: Filling an array at compile time
On Wednesday, 9 February 2022 at 10:25:34 UTC, bauss wrote: Is it guaranteed that the value is initialized at compiletime however? yes, D guarentees this at 100%.
Re: Filling an array at compile time
On Wednesday, 9 February 2022 at 10:01:15 UTC, Anonymouse wrote:
On Wednesday, 9 February 2022 at 08:12:52 UTC, Vindex wrote:
[...]
I would do this.
```
import std;
alias Record = Tuple!(string, string, string);
static immutable string[][] table = () {
string[][] table;
string csvText = import("file.csv");
foreach (record; csvReader!Record(csvText)) {
table ~= [record[0], record[1], record[2]];
}
return table;
}();
pragma(msg, table); // Available at compile-time
void main() {
writeln(table);
}
```
And then `-J{path}` to tell the compiler where to find
`file.csv`.
```
dmd -J. csv.d
```
Thanks! It does indeed work at compile time.
Re: how to handle very large array?
On Wednesday, 9 February 2022 at 10:29:03 UTC, ag0aep6g wrote: Try to think of a more efficient way of storing the information. I cant agree more. The problem of OP is not dynamic arrays, it's that he uses an inadequate data structure.
Re: how to handle very large array?
On Wednesday, 9 February 2022 at 10:03:21 UTC, MichaelBi wrote: day6 of the advent of code 2021 needs to handle an array of 10^12 length, or even bigger... plus change elements and append elements. normal implementation such as length, appender and ref element etc, seems cannot handle that big array? is there any alternative data structure or algorithm can handle such large array properly? thanks. Use a memorymapped file that holds the array values, in theory it can be infinite then. Since an array has a known size for each entry then you can treat the file as an array. Let's say you have an array of ints. For a memorymapped file you obviously only have bytes to work with, so each entry will be 4 bytes, since a 32 bit integer (int) is 4 bytes. So to read something at a specific index you simply do N x I where N is the size of the type and I is the index you want to read at. Otherwise the size of an array cannot exceed the RAM you have, if your system can't use diskspace as RAM of course.
Re: how to handle very large array?
On 09.02.22 11:09, MichaelBi wrote: On Wednesday, 9 February 2022 at 10:05:23 UTC, MichaelBi wrote: [...] got outofmemory error: core.exception.OutOfMemoryError@src\core\lifetime.d(126): Memory allocation failed https://adventofcode.com/2021/day/6#part2 "Suppose the lanternfish live forever and have unlimited food and space. Would they take over the entire ocean? After 256 days in the example above, there would be a total of 26984457539 lanternfish! How many lanternfish would there be after 256 days" 26984457539 in above is the array length. If you store one byte per lanternfish, that's 25 GiB. You don't seem to have enough RAM for such a large array. Try to think of a more efficient way of storing the information.
Re: Filling an array at compile time
On Wednesday, 9 February 2022 at 10:01:15 UTC, Anonymouse wrote:
On Wednesday, 9 February 2022 at 08:12:52 UTC, Vindex wrote:
Will the loop (foreach) run at compile time? How can I make it
work at compile time?
```
import std.csv, std.stdio;
alias Record = Tuple!(string, string, string);
immutable string[][] table;
shared static this() {
string csvText = import("file.csv");
foreach (record; csvReader!Record(csvText)) {
table ~= [record[0], record[1], record[2]];
}
}
void main() {
writeln(table):
}
```
I would do this.
```
import std;
alias Record = Tuple!(string, string, string);
static immutable string[][] table = () {
string[][] table;
string csvText = import("file.csv");
foreach (record; csvReader!Record(csvText)) {
table ~= [record[0], record[1], record[2]];
}
return table;
}();
pragma(msg, table); // Available at compile-time
void main() {
writeln(table);
}
```
And then `-J{path}` to tell the compiler where to find
`file.csv`.
```
dmd -J. csv.d
```
Is it guaranteed that the value is initialized at compiletime
however?
Something being available at compiletime isn't the same as being
initialized at compiletime only.
If it's guaranteed then that's indeed the best solution.
Re: how to handle very large array?
On Wednesday, 9 February 2022 at 10:03:21 UTC, MichaelBi wrote: day6 of the advent of code 2021 needs to handle an array of 10^12 length, or even bigger... plus change elements and append elements. normal implementation such as length, appender and ref element etc, seems cannot handle that big array? is there any alternative data structure or algorithm can handle such large array properly? thanks. got outofmemory error: core.exception.OutOfMemoryError@src\core\lifetime.d(126): Memory allocation failed
Re: how to handle very large array?
On Wednesday, 9 February 2022 at 10:05:23 UTC, MichaelBi wrote: On Wednesday, 9 February 2022 at 10:03:21 UTC, MichaelBi wrote: day6 of the advent of code 2021 needs to handle an array of 10^12 length, or even bigger... plus change elements and append elements. normal implementation such as length, appender and ref element etc, seems cannot handle that big array? is there any alternative data structure or algorithm can handle such large array properly? thanks. got outofmemory error: core.exception.OutOfMemoryError@src\core\lifetime.d(126): Memory allocation failed https://adventofcode.com/2021/day/6#part2 "Suppose the lanternfish live forever and have unlimited food and space. Would they take over the entire ocean? After 256 days in the example above, there would be a total of 26984457539 lanternfish! How many lanternfish would there be after 256 days" 26984457539 in above is the array length.
Re: Filling an array at compile time
On Wednesday, 9 February 2022 at 08:12:52 UTC, Vindex wrote:
Will the loop (foreach) run at compile time? How can I make it
work at compile time?
```
import std.csv, std.stdio;
alias Record = Tuple!(string, string, string);
immutable string[][] table;
shared static this() {
string csvText = import("file.csv");
foreach (record; csvReader!Record(csvText)) {
table ~= [record[0], record[1], record[2]];
}
}
void main() {
writeln(table):
}
```
I would do this.
```
import std;
alias Record = Tuple!(string, string, string);
static immutable string[][] table = () {
string[][] table;
string csvText = import("file.csv");
foreach (record; csvReader!Record(csvText)) {
table ~= [record[0], record[1], record[2]];
}
return table;
}();
pragma(msg, table); // Available at compile-time
void main() {
writeln(table);
}
```
And then `-J{path}` to tell the compiler where to find `file.csv`.
```
dmd -J. csv.d
```
how to handle very large array?
day6 of the advent of code 2021 needs to handle an array of 10^12 length, or even bigger... plus change elements and append elements. normal implementation such as length, appender and ref element etc, seems cannot handle that big array? is there any alternative data structure or algorithm can handle such large array properly? thanks.
Re: Filling an array at compile time
On Wednesday, 9 February 2022 at 08:12:52 UTC, Vindex wrote:
Will the loop (foreach) run at compile time? How can I make it
work at compile time?
```
import std.csv, std.stdio;
alias Record = Tuple!(string, string, string);
immutable string[][] table;
shared static this() {
string csvText = import("file.csv");
foreach (record; csvReader!Record(csvText)) {
table ~= [record[0], record[1], record[2]];
}
}
void main() {
writeln(table):
}
```
It will not run at compile-time because csvText is a runtime
variable. It should be enum to be accessible at compile-time.
The second issue is that your foreach should probably be static
foreach.
The third issue is how you're creating "table". The append
operation will be executed at runtime, which means that even if
the loop runs at compile-time then you're effectively not winning
anything and it basically just becomes a loop-unroll manually
done.
The solution would be to create a function that returns a string
that is equivalent to the contents of the array you want to
create, as if you wrote the content yourself.
And then simply using mixin to "set" the value of the table by
calling that function.
Ex.
```
string getInt() { return "immutable a = 10;"; }
mixin(getInt);
// The variable a is accessible here ...
```
Re: How to verify DMD download with GPG?
On Tuesday, 8 February 2022 at 20:15:50 UTC, forkit wrote: btw. the key is listed there - not sure what you mean. I didn't see "3AAF1A18E61F6FAA3B7193E4DB8C5218B9329CF8" on the listing on the webpage https://dlang.org/gpg_keys.html That pages is not similar to what I get with "--list-keys --with-subkey-fingerprints". ``` pub rsa4096 2014-09-01 [SC] [expired: 2020-03-25] AFC7DB45693D62BB472BF27BAB8FE924C2F7E724 uid [ expired] Martin Nowak (dawg) uid [ expired] Martin Nowak uid [ expired] Martin Nowak uid [ expired] Martin Nowak pub rsa2048 2016-01-29 [SC] BBED1B088CED7F958917FBE85004F0FAD051576D uid [ unknown] Vladimir Panteleev sub rsa2048 2016-01-29 [E] AB78BAC596B648B59A41983A3850E93043EBB12C pub rsa4096 2015-11-24 [SC] [expires: 2026-03-23] 8FDB8D357AF468A9428ACE3C2055F76601A36FB0 uid [ unknown] Sebastian Wilzbach uid [ unknown] Sebastian Wilzbach pub rsa4096 2018-03-26 [SC] [expired: 2020-03-25] F77158814C19E5E07BA1079A65394AFEF4A68565 uid [ expired] DLang Nightly (bot) pub rsa4096 2020-03-12 [SC] [expires: 2022-03-12] F46A10D0AB44C3D15DD65797BCDD73FFC3EB6146 uid [ unknown] Martin Nowak uid [ unknown] Martin Nowak uid [ unknown] Martin Nowak sub rsa4096 2020-03-12 [E] [expires: 2022-03-12] B92614C21EC5779DC678468E9A813AD3C11508BC sub rsa4096 2020-03-12 [S] [expires: 2022-03-12] 3AAF1A18E61F6FAA3B7193E4DB8C5218B9329CF8 ``` The last two lines on the webpage are: ``` sub rsa4096/0x9A813AD3C11508BC 2020-03-12 [E] [expires: 2022-03-12] sub rsa4096/0xDB8C5218B9329CF8 2020-03-12 [S] [expires: 2022-03-12] ``` That is why I thought something was wrong.
Filling an array at compile time
Will the loop (foreach) run at compile time? How can I make it
work at compile time?
```
import std.csv, std.stdio;
alias Record = Tuple!(string, string, string);
immutable string[][] table;
shared static this() {
string csvText = import("file.csv");
foreach (record; csvReader!Record(csvText)) {
table ~= [record[0], record[1], record[2]];
}
}
void main() {
writeln(table):
}
```
