Re: Help optimize D solution to phone encoding problem: extremely slow performace.
On Tuesday, 16 January 2024 at 22:13:55 UTC, H. S. Teoh wrote: used for the recursive calls. Getting rid of the .format ought to speed it up a bit. Will try that now... That will make no difference for the `count` option which is where your solution was very slow. To run the slow test manually use the `words_quarter.txt` dictionary (the phone numbers file doesn't matter much - it's all in the dictionary). But pls run the benchmarks yourself as I am not going to keep running it for you, and would be nice if you posted your solution on a Gist for example, pasting lots of code in the forum makes it difficult to follow.
Re: Help optimize D solution to phone encoding problem: extremely slow performace.
On Tuesday, 16 January 2024 at 22:15:04 UTC, Siarhei Siamashka
wrote:
On Tuesday, 16 January 2024 at 21:15:19 UTC, Renato wrote:
For the record (I already posted this on GitHub)... here's [my
current fastest
solution](https://github.com/renatoathaydes/prechelt-phone-number-encoding/blob/dlang-key-hash-incremental/src/d/src/dencoder.d) time using the same algorithm as Rust ...
[...]
... what I am really curious about is what the code I wrote is
doing wrong that causes it to run 4x slower than Rust despite
doing "the same thing"...
It's a GC allocations fest. Things like this make it slow:
```diff
{
-string digit = [digits[0]];
+string digit = digits[0 .. 1];
words.insertBack(digit);
```
I was under the impression that `[digits[0]]` would just use a
stack allocation??
The profiler does not show any GC anymore, are you sure it's a
"GC allocations fest"???
And at the top is the associative array lookup (when profiling
the handling of the "phones_1_000_000_with_empty.txt" input
file):
```
36.85% dencoder dencoder [.] _aaInX
12.38% dencoder dencoder [.] void
Well, I know, but I did everything to make the hash "cheap" to
compute so I still don't see a way to improve it.
Re: Would you recommend TDPL today?
On Tuesday, 16 January 2024 at 02:25:32 UTC, matheus wrote: ... I'll reply to myself but I just would like to say thanks to Jonathan M Davis and Mike Shah. I started with TDPL but I'll fill my knowledge with the other suggestions you gave me. Thanks again, Matheus.
Re: Understanding the Use of Nested Import and Selective Import in D
On Tuesday, January 16, 2024 1:42:04 PM MST bomat via Digitalmars-d-learn wrote: > Wow, that was... exhaustive. Thanks for that. :) > One more question that I have, though... > > On Tuesday, 16 January 2024 at 19:05:43 UTC, Jonathan M Davis > > wrote: > > The downside of course is that you then have import statements > > throughout your code, and they're often going to be duplicated > > throughout a module (or even within a function if you localize > > them far enough), because separate parts of the code then need > > their own local imports. > > Apart from the aesthetic "clutter" of duplicate imports, will > they also put additional strain on the compiler and/or affect the > resulting binary? I mean, will the imports actually be compiled > in several times? Imports are never compiled in. Importing a D module is nothing like #including a C/C++ header file. It does not result in any code being inserted into the current module, and if it results in anything being added to the binary, it's because a template from that module was instantiated with a new set of arguments, resulting in a new template instantiation that has to end up in the binary. An import statement tells the compiler to allow the current code to use the symbols from the imported module. That requires compiling the imported module sufficiently for the compiler to then let those symbols be correctly used within the module that's doing the importing, but importing a module doesn't make it so that the compiler fully compiles the imported module. To do that, the module has to also be passed to the compiler to be compiled (be it as part of the same compilation process or compiled separately to be linked in later). And once a module has been imported, the compiler has already built the symbol table for that module, so importing the module additional times during the same round of compilation will not result in it being processed again. The import statement will need to be parsed, which isn't free, but it's so cheap in comparison to everything else that you'd likely have a very hard time detecting the cost even in a very large codebase with a lot of local import statements. And if anything, using local imports could reduce compilation times, because if an import is local to a template, and your code doesn't end up instantiating that template (or doesn't compile in a particular branch of a static if or version block), then the compiler doesn't need to do anything with that import. - Jonathan M Davis
Re: Help optimize D solution to phone encoding problem: extremely slow performace.
On Tue, Jan 16, 2024 at 10:15:04PM +, Siarhei Siamashka via
Digitalmars-d-learn wrote:
> On Tuesday, 16 January 2024 at 21:15:19 UTC, Renato wrote:
[...]
> > ... what I am really curious about is what the code I wrote is doing
> > wrong that causes it to run 4x slower than Rust despite doing "the
> > same thing"...
>
> It's a GC allocations fest.
Indeed.
I have just completed 2 rounds of optimizations of my version of the
code, and both times the profiler also showed the problem to be
excessive allocations in the inner loop. So, I did the following
optimizations:
1) Get rid of .format in the inner loop. Not only does .format cause a
lot of allocations, it is also a known performance hog. So instead
of constructing the output string in the search function, I changed it
to take a delegate instead, and the delegate either counts the result or
prints it directly (bypassing the construction of an intermediate
string). This improved performance quite a bit for the count-only runs,
but also wins some performance even when output is generated. Overall,
however, this optimization only gave me some minor savings.
2) Changed the `path` parameter from string[] to string, since I didn't
really need it to be an array of strings anyway. This in itself only
improved performance marginally, barely noticeable, but it led to (3),
which gave a huge performance boost.
3) Basically, in the earlier version of the code, the `path` parameter
was appended to every time I recursed, and furthermore the same initial
segment gets appended to many times with different trailers as the
algorithm walks the trie. As a result, this triggers a lot of array
reallocations to store the new strings. Most of these allocations are
unnecessary, because we already know that the initial segment of the
string will stay constant, only the tail end changes. Furthermore, we
only ever have a single instance of .path at any point in time in the
algorithm. So we could use a single buffer to hold all of these
instances of .path, and simply return slices to it as we go along,
overwriting the tail end each time we need to append something.
This significantly cut down on the number of allocations, and along
with (1) and (2), performance improved by about 3x (!). It didn't
completely remove all allocations, but I'm reasonably happy with the
performance now that I probably won't try to optimize it more unless
it's still losing out to another language. ;-)
(I'm especially curious to see if this beats the Rust version. :-P)
Optimized version of the code:
---snip
/**
* Encoding phone numbers according to a dictionary.
*/
import std;
/**
* Table of digit mappings.
*/
static immutable ubyte[dchar] digitOf;
shared static this()
{
digitOf = [
'E': 0,
'J': 1, 'N': 1, 'Q': 1,
'R': 2, 'W': 2, 'X': 2,
'D': 3, 'S': 3, 'Y': 3,
'F': 4, 'T': 4,
'A': 5, 'M': 5,
'C': 6, 'I': 6, 'V': 6,
'B': 7, 'K': 7, 'U': 7,
'L': 8, 'O': 8, 'P': 8,
'G': 9, 'H': 9, 'Z': 9,
];
}
/**
* Trie for storing dictionary words according to the phone number mapping.
*/
class Trie
{
Trie[10] edges;
string[] words;
private void insert(string word, string suffix)
{
const(ubyte)* dig;
while (!suffix.empty &&
(dig = std.ascii.toUpper(suffix[0]) in digitOf) is null)
{
suffix = suffix[1 .. $];
}
if (suffix.empty)
{
words ~= word;
return;
}
auto node = new Trie;
auto idx = *dig;
if (edges[idx] is null)
{
edges[idx] = new Trie;
}
edges[idx].insert(word, suffix[1 .. $]);
}
/**
* Insert a word into the Trie.
*
* Characters that don't map to any digit are ignored in building the Trie.
* However, the original form of the word will be retained as-is in the
* leaf node.
*/
void insert(string word)
{
insert(word, word[]);
}
/**
* Iterate over all words stored in this Trie.
*/
void foreachEntry(void delegate(string path, string word) cb)
{
void impl(Trie node, string path = "")
{
if (node is null) return;
foreach (word; node.words)
{
cb(path, word);
}
foreach (i, child; node.edges)
{
impl(child, path ~ cast(char)('0' + i));
}
}
impl(this);
}
}
/**
* Loads the given dictionary into a Trie.
*/
Trie loadDictionary(R)(R lines)
if (isInputRange!R & is(ElementType!R : const(char)[]))
{
Trie result = new Trie;
foreach (line; lines)
{
result.insert(line.idup);
}
return result;
}
///
unittest
{
auto dict = loadDictionary(q"ENDDICT
an
blau
Bo"
Boot
bo"s
da
Fee
fern
Fest
fort
je
jemand
mir
Mix
Mixer
Re: Help optimize D solution to phone encoding problem: extremely slow performace.
On Tuesday, 16 January 2024 at 21:15:19 UTC, Renato wrote:
For the record (I already posted this on GitHub)... here's [my
current fastest
solution](https://github.com/renatoathaydes/prechelt-phone-number-encoding/blob/dlang-key-hash-incremental/src/d/src/dencoder.d) time using the same algorithm as Rust ...
[...]
... what I am really curious about is what the code I wrote is
doing wrong that causes it to run 4x slower than Rust despite
doing "the same thing"...
It's a GC allocations fest. Things like this make it slow:
```diff
{
-string digit = [digits[0]];
+string digit = digits[0 .. 1];
words.insertBack(digit);
```
And at the top is the associative array lookup (when profiling
the handling of the "phones_1_000_000_with_empty.txt" input file):
```
36.85% dencoder dencoder [.] _aaInX
12.38% dencoder dencoder [.] void
dencoder.printTranslations(immutable(char)[][][dencoder.Key],
dencoder.ISolutionHandler, immutable(char)[], immutable(char)[],
std.container.array.Array!(immutable(char)[]).Array)
6.43% dencoder dencoder [.] nothrow @nogc
scope void core.internal.gc.impl.conservative.gc.Gcx.mark!(false,
true,
true).mark(core.internal.gc.impl.conservative.gc.Gcx.ScanRange!(false).ScanRange)
4.53% dencoder dencoder [.] pure @safe void
std.algorithm.iteration.FilterResult!(dencoder.main(immutable(char)[][]).__lambda12, immutable(char)[]).FilterResult.popFront()
4.08% dencoder dencoder [.]
_d_array_slice_copy
2.43% dencoder dencoder [.] _d_newarrayU
2.21% dencoder dencoder [.] shared nothrow
@nogc @trusted void core.internal.spinlock.SpinLock.lock()
2.00% dencoder dencoder [.] pure @safe void
std.array.Appender!(immutable(char)[]).Appender.put!(dchar).put(dchar)
1.91% dencoder dencoder [.] nothrow void*
core.internal.gc.impl.conservative.gc.Gcx.smallAlloc(ulong, ref
ulong, uint, const(TypeInfo))
1.67% dencoder dencoder [.]
_DThn16_4core8internal2gc4impl12conservativeQw14ConservativeGC6qallocMFNbmkMxC8TypeInfoZSQDd6memory8BlkInfo_
1.66% dencoder dencoder [.] pure nothrow
@nogc scope @trusted ulong
core.internal.gc.bits.GCBits.setLocked(ulong)
1.60% dencoder dencoder [.] const pure
nothrow @trusted ulong object.TypeInfo_Struct.getHash(scope
const(void*))
1.53% dencoder dencoder [.] nothrow @safe
void
core.internal.util.array.enforceRawArraysConformable(const(char[]), const(ulong), const(void[]), const(void[]), const(bool))
1.49% dencoder dencoder [.] nothrow void*
core.internal.gc.impl.conservative.gc.ConservativeGC.runLocked!(core.internal.gc.impl.conservative.gc.ConservativeGC.mallocNoSync(ulong, uint, ref ulong, const(TypeInfo)), core.internal.gc.impl.conservative.gc.mallocTime, core.internal.gc.impl.conservative.gc.numMallocs, ulong, uint, ulong, const(TypeInfo)).runLocked(ref ulong, ref uint, ref ulong, ref const(TypeInfo))
1.27% dencoder dencoder [.] pure nothrow
@safe void
std.array.Appender!(immutable(char)[]).Appender.ensureAddable(ulong)
0.81% dencoder dencoder [.] pure @property
@safe dchar
std.algorithm.iteration.FilterResult!(dencoder.main(immutable(char)[][]).__lambda12, immutable(char)[]).FilterResult.front()
0.79% dencoder dencoder [.] nothrow @safe
void core.internal.util.array._enforceNoOverlap(const(char[]),
ulong, ulong, const(ulong))
0.74% dencoder dencoder [.] nothrow void
core.internal.gc.impl.conservative.gc.Pool.setBits(ulong, uint)
0.73% dencoder dencoder [.] pure @safe void
std.array.Appender!(immutable(char)[]).Appender.put!(std.algorithm.iteration.FilterResult!(dencoder.main(immutable(char)[][]).__lambda12, immutable(char)[]).FilterResult).put(std.algorithm.iteration.FilterResult!(dencoder.main(immutable(char)[][]).__lambda12, immutable(char)[]).FilterResult)
0.70% dencoder dencoder [.] pure @safe ulong
std.range.primitives.walkLength!(std.algorithm.iteration.FilterResult!(dencoder.main(immutable(char)[][]).__lambda12, immutable(char)[]).FilterResult).walkLength(std.algorithm.iteration.FilterResult!(dencoder.main(immutable(char)[][]).__lambda12, immutable(char)[]).FilterResult)
0.60% dencoder dencoder [.] bool
dencoder.lastItemIsDigit(std.container.array.Array!(immutable(char)[]).Array)
0.54% dencoder dencoder [.] _d_newarrayT
[...]
```
Re: Help optimize D solution to phone encoding problem: extremely slow performace.
On Tue, Jan 16, 2024 at 09:15:19PM +, Renato via Digitalmars-d-learn wrote: > On Tuesday, 16 January 2024 at 20:34:48 UTC, H. S. Teoh wrote: > > On Tue, Jan 16, 2024 at 12:28:49PM -0800, H. S. Teoh via > > Digitalmars-d-learn wrote: [...] > > > Anyway, I've fixed the problem, now my program produces the exact > > > same output as Renato's repo. Code is posted below. > > [...] > > > > Great, I ran the benchmarks for you :) > > I had to change how you accept arguments, even though you did "the > right thing" using `getopt`, the solutions should just take a `count` > or `print` argument first... Oops, haha :-P > Anyway, here's your result: > > ``` > ===> ./rust > ./rust,24133632,25 > ./rust,24739840,130 > ./rust,24477696,536 > ./rust,25247744,1064 > ./rust,8175616,6148 > ./rust,8306688,8315 > ===> src/d/dencoder > src/d/dencoder,46055424,43 > src/d/dencoder,96337920,146 > src/d/dencoder,102350848,542 > src/d/dencoder,102268928,1032 > src/d/dencoder,40206336,99936 > ^C > ``` > > It took too long with the `count` option, so I had to abort before the > last run ended... there's probably some bug there, otherwise the Trie > runs very fast, as I had expected. [...] Do you have the problematic data file handy? I'd like to look into any potential bugs. Also, the profiler revealed that a lot of time was spent in the GC and in small allocations. The cause is in all likelihood the .format() call for each found match, and array append being used for the recursive calls. Getting rid of the .format ought to speed it up a bit. Will try that now... T -- If the comments and the code disagree, it's likely that *both* are wrong. -- Christopher
Re: Help optimize D solution to phone encoding problem: extremely slow performace.
On Tuesday, 16 January 2024 at 21:15:19 UTC, Renato wrote: I can't explain why it's so incredibly fast, specially for the `count` case. I tried using the same hashing function on my solution, but that didn't really help me! That's dynamic programming with memoization. Basically caching the already calculated results (in the `dp` array) and avoiding recalculations when the recursive function revisits the same state again.
Re: Help optimize D solution to phone encoding problem: extremely slow performace.
On Tuesday, 16 January 2024 at 20:34:48 UTC, H. S. Teoh wrote: On Tue, Jan 16, 2024 at 12:28:49PM -0800, H. S. Teoh via Digitalmars-d-learn wrote: [...] Anyway, I've fixed the problem, now my program produces the exact same output as Renato's repo. Code is posted below. [...] Great, I ran the benchmarks for you :) I had to change how you accept arguments, even though you did "the right thing" using `getopt`, the solutions should just take a `count` or `print` argument first... Anyway, here's your result: ``` ===> ./rust ./rust,24133632,25 ./rust,24739840,130 ./rust,24477696,536 ./rust,25247744,1064 ./rust,8175616,6148 ./rust,8306688,8315 ===> src/d/dencoder src/d/dencoder,46055424,43 src/d/dencoder,96337920,146 src/d/dencoder,102350848,542 src/d/dencoder,102268928,1032 src/d/dencoder,40206336,99936 ^C ``` It took too long with the `count` option, so I had to abort before the last run ended... there's probably some bug there, otherwise the Trie runs very fast, as I had expected. For the record (I already posted this on GitHub)... here's [my current fastest solution](https://github.com/renatoathaydes/prechelt-phone-number-encoding/blob/dlang-key-hash-incremental/src/d/src/dencoder.d) time using the same algorithm as Rust (after I fixed my solution that was using `int128`, which was not valid, as @ssvb pointed out): ``` Proc,Run,Memory(bytes),Time(ms) ===> ./rust ./rust,23986176,24 ./rust,24346624,118 ./rust,24543232,525 ./rust,24346624,1027 ./rust,8011776,3830 ./rust,8486912,18403 ===> src/d/dencoder src/d/dencoder,13615104,30 src/d/dencoder,24723456,374 src/d/dencoder,24592384,1750 src/d/dencoder,24788992,3472 src/d/dencoder,11517952,10235 src/d/dencoder,11517952,51211 ``` Not great :( But @ssvb came up with a really fast implementation, though totally different algorithm (so dont' take this as evidence of D being faster than Rust or anything like that): ``` Proc,Run,Memory(bytes),Time(ms) ===> ./rust ./rust,23986176,24 ./rust,24461312,135 ./rust,24494080,514 ./rust,24526848,981 ./rust,8175616,3647 ./rust,8011776,15404 ===> src/d/dencoder src/d/dencoder,16433152,30 src/d/dencoder,16613376,125 src/d/dencoder,16613376,468 src/d/dencoder,16613376,941 src/d/dencoder,5570560,12 src/d/dencoder,6701056,18 ``` I can't explain why it's so incredibly fast, specially for the `count` case. I tried using the same hashing function on my solution, but that didn't really help me! Pretty cool to see different solutions to the problem, but I'm still curious to know where the solution I wrote is being slow compared to Rust which is using identical, to my understanding, code! I'm sure people could write incredibly fast code to solve this problem, but what I am really curious about is what the code I wrote is doing wrong that causes it to run 4x slower than Rust despite doing "the same thing"...
Re: Understanding the Use of Nested Import and Selective Import in D
Wow, that was... exhaustive. Thanks for that. :) One more question that I have, though... On Tuesday, 16 January 2024 at 19:05:43 UTC, Jonathan M Davis wrote: The downside of course is that you then have import statements throughout your code, and they're often going to be duplicated throughout a module (or even within a function if you localize them far enough), because separate parts of the code then need their own local imports. Apart from the aesthetic "clutter" of duplicate imports, will they also put additional strain on the compiler and/or affect the resulting binary? I mean, will the imports actually be compiled in several times?
Re: Socket handle leak and active handle warning with Vibe-D
On Monday, 15 January 2024 at 22:19:56 UTC, Steven Schveighoffer wrote: You may have to do the same thing I did with redis: https://github.com/vibe-d/vibe.d/pull/2372 Good luck! I would also say, I don't know why Windows doesn't do the same trace info debug thing, except that probably whomever added it didn't care about windows. Many thanks for the assistance.
Re: Help optimize D solution to phone encoding problem: extremely slow performace.
On Tue, Jan 16, 2024 at 12:28:49PM -0800, H. S. Teoh via Digitalmars-d-learn
wrote:
[...]
> Anyway, I've fixed the problem, now my program produces the exact same
> output as Renato's repo. Code is posted below.
[...]
Oops, forgot to actually paste the code. Here it is:
snip
/**
* Encoding phone numbers according to a dictionary.
*/
import std;
/**
* Table of digit mappings.
*/
static immutable ubyte[dchar] digitOf;
shared static this()
{
digitOf = [
'E': 0,
'J': 1, 'N': 1, 'Q': 1,
'R': 2, 'W': 2, 'X': 2,
'D': 3, 'S': 3, 'Y': 3,
'F': 4, 'T': 4,
'A': 5, 'M': 5,
'C': 6, 'I': 6, 'V': 6,
'B': 7, 'K': 7, 'U': 7,
'L': 8, 'O': 8, 'P': 8,
'G': 9, 'H': 9, 'Z': 9,
];
}
/**
* Trie for storing dictionary words according to the phone number mapping.
*/
class Trie
{
Trie[10] edges;
string[] words;
private void insert(string word, string suffix)
{
const(ubyte)* dig;
while (!suffix.empty &&
(dig = std.ascii.toUpper(suffix[0]) in digitOf) is null)
{
suffix = suffix[1 .. $];
}
if (suffix.empty)
{
words ~= word;
return;
}
auto node = new Trie;
auto idx = *dig;
if (edges[idx] is null)
{
edges[idx] = new Trie;
}
edges[idx].insert(word, suffix[1 .. $]);
}
/**
* Insert a word into the Trie.
*
* Characters that don't map to any digit are ignored in building the Trie.
* However, the original form of the word will be retained as-is in the
* leaf node.
*/
void insert(string word)
{
insert(word, word[]);
}
/**
* Iterate over all words stored in this Trie.
*/
void foreachEntry(void delegate(string path, string word) cb)
{
void impl(Trie node, string path = "")
{
if (node is null) return;
foreach (word; node.words)
{
cb(path, word);
}
foreach (i, child; node.edges)
{
impl(child, path ~ cast(char)('0' + i));
}
}
impl(this);
}
}
/**
* Loads the given dictionary into a Trie.
*/
Trie loadDictionary(R)(R lines)
if (isInputRange!R & is(ElementType!R : const(char)[]))
{
Trie result = new Trie;
foreach (line; lines)
{
result.insert(line.idup);
}
return result;
}
///
unittest
{
auto dict = loadDictionary(q"ENDDICT
an
blau
Bo"
Boot
bo"s
da
Fee
fern
Fest
fort
je
jemand
mir
Mix
Mixer
Name
neu
o"d
Ort
so
Tor
Torf
Wasser
ENDDICT".splitLines);
auto app = appender!(string[]);
dict.foreachEntry((path, word) { app ~= format("%s: %s", path, word); });
assert(app.data == [
"10: je",
"105513: jemand",
"107: neu",
"1550: Name",
"253302: Wasser",
"35: da",
"38: so",
"400: Fee",
"4021: fern",
"4034: Fest",
"482: Tor",
"4824: fort",
"4824: Torf",
"51: an",
"562: mir",
"562: Mix",
"56202: Mixer",
"78: Bo\"",
"783: bo\"s",
"7857: blau",
"7884: Boot",
"824: Ort",
"83: o\"d"
]);
}
/**
* Find all encodings of the given phoneNumber according to the given
* dictionary, and write each encoding to the given sink.
*/
void findMatches(W)(Trie dict, const(char)[] phoneNumber, W sink)
if (isOutputRange!(W, string))
{
bool impl(Trie node, const(char)[] suffix, string[] path, bool allowDigit)
{
if (node is null)
return false;
// Ignore non-digit characters in phone number
while (!suffix.empty && (suffix[0] < '0' || suffix[0] > '9'))
suffix = suffix[1 .. $];
if (suffix.empty)
{
// Found a match, print result
foreach (word; node.words)
{
put(sink, format("%s: %-(%s %)", phoneNumber,
path.chain(only(word;
}
return !node.words.empty;
}
bool ret;
foreach (word; node.words)
{
// Found a matching word, try to match the rest of the phone
// number.
ret = true;
if (impl(dict, suffix, path ~ word, true))
allowDigit = false;
}
if (impl(node.edges[suffix[0] - '0'], suffix[1 .. $], path, false))
{
allowDigit = false;
ret = true;
}
if (allowDigit)
{
// If we got here, it means that if we take the current node as the
// next word choice, then the following digit will have no further
// matches, and we may encode it as a single digit.
auto nextSuffix = suffix[1 .. $];
Re: Help optimize D solution to phone encoding problem: extremely slow performace.
On Tue, Jan 16, 2024 at 06:54:56PM +, Renato via Digitalmars-d-learn wrote: > On Tuesday, 16 January 2024 at 16:56:04 UTC, Siarhei Siamashka wrote: [...] > > You are not allowed to emit "1" as the first token in the output as > > long as there are any dictionary word matches at that position. The > > relevant paragraph from the problem statement: Ohhh now I get it. Initially I misunderstood that as saying that if the rest of the phone number has at least one match, then a digit is not allowed. Now I see that what it's actually saying is that even if some random dictionary word matches at that position, even if it does not lead to any full matches, then a digit is excluded. [...] > > I also spent a bit of time trying to figure out this nuance when > > implementing my solution. It doesn't make much sense visually (no > > back-to-back digits in the output either way), but that's how it is. > > Exactly, this is one of the things that make this problem a bit > annoying to solve :) It's a strange requirement, for sure, but I don't think it's annoying. It makes the problem more Interesting(tm). ;-) Anyway, I've fixed the problem, now my program produces the exact same output as Renato's repo. Code is posted below. Interestingly enough, the running time has now halved to about 0.9 seconds for 1 million phone numbers. I guess that's caused by the more stringent requirement excluding many more matching possibilities, effectively pruning away large parts of the search tree. > @"H. S. Teoh" you implemented the solution as a Trie!! Nice, that's > also what I did when I "participated" in the study. Here's [my Trie > solution in > Java](https://github.com/renatoathaydes/prechelt-phone-number-encoding/blob/fastest-implementations-print-or-count/src/java/Main.java). > > These are basically the two common approaches to the problem: a Trie > or a numeric-based table. According to the study, people who use > scripting languages almost always go with the numeric approach, while > people coming from lower level languages tend to use a data structure > like Trie (if they don't know Trie, they come up with something > similar which is fascinating), which is harder to implement but more > efficient in general. Interesting. I guess my C/C++ background is showing. ;-) I'm not sure what exactly motivated me to go this route; I guess it was just my default preference of choosing the path of least work as far as the algorithm is concerned: I chose the algorithm that did the least amount of work needed to produce the right answer. Scanning through sections of the dictionary to find a match was therefore excluded; so my first thought was an AA. But then how much of the initial prefix to look up an in AA? Since it can't be known beforehand, I'd have to gradually lengthen the prefix to search for, which does a lot of repetitive work (we keep looking up the first few digits repeatedly each time we search for a longer prefix). Plus, multiple consecutive AA lookups is not cache-friendly. So my next thought was, what should I do such that I don't have to look at the initial digits anymore once I already processed it? This line of thought naturally led to a trie structure. Once I arrived at a trie structure, the next question was how exactly dictionary entries would be stored in it. Again, in the vein of doing the least amount of work I could get away with, I thought, if I stored words in the trie directly, with each edge encoding a letter, then during the search I'd have to repeatedly convert letters to the corresponding phone number digit and vice versa. So why not do this conversion beforehand, and store only phone digits in the trie? This also had the additional benefit of letting me effectively search multiple letters simultaneously, since multiple letters map to the same digit, so scanning a digit is equivalent to searching multiple letters at the same time. The output, of course, required the original form of the words -- so the obvious solution was to attach the original words as a list of words attached to the trie node representing the end of that word. Once this was all decided, the only remaining question was the search algorithm. This turned out to take the most time in solving this problem, due to the recursive nature of the search, I had to grapple with where and how to make the recursive calls, and how to propagate return values correctly. The initial implementation only found word matches, and did not allow the single digits. Happily, the recursive algorithm turned out to have enough structure to encode the single digit requirements as well, although it took a bit of trial and error to find the correct implementation. > Can I ask you why didn't you use the [D stdlib > Trie](https://dlang.org/phobos/std_uni.html#codepointTrie)? Not sure > that would've worked, but did you consider that? Haha, I didn't even think of that. :-D I wouldn't have wanted to use it anyway, because it was optimized for
Re: Understanding the Use of Nested Import and Selective Import in D
On Tuesday, January 16, 2024 6:19:59 AM MST Orfeo via Digitalmars-d-learn
wrote:
> I found myself a bit perplexed when it comes to the usage of
> "nested imports" and selective imports. It seems that prominent D
> programmers have varied opinions on the matter. I would love to
> hear your insights and experiences on this topic.
>
> Here's a quick summary of what I've come across from three
> influential D programmers:
>
> - Adam Ruppe: In his blog post titled [D's selective imports have
> effects you may not
> want](http://dpldocs.info/this-week-in-arsd/Blog.Posted_2023_11_06.html)
> have effects you may not want, Adam advises against the use of selective
> imports. He highlights potential unwanted side effects and suggests caution
> when employing them.
>
> - Atila Neves: At DConf 2023, Atila Neves recommended the use of
> nested imports. He argues that nested imports can make
> refactoring easier and help in assessing the dependencies a
> function has.
>
> - Rober Schadek: Also at DConf 2023, Rober Schadek discouraged
> the use of nested imports, taking a stance different from Atila
> Neves.
>
> Now, the big question is: What's your preferred approach?
When local imports were introduced, they were pushed as best practice (in
part, because Andrei is a big fan of them), and I think that for the most
part, they still are, but there's definitely going to be some disagreement
on it.
The benefits of local imports have to do with encapsulation. When you
localize an import as much as possible, you make it clear which parts of the
code are using that import. That makes it easier to see which imports are
used by a section of code and where symbols are coming from. It also makes
it much easier to refactor imports, because you can see what's using the
import and see whether it's still needed, whereas if an import is put at the
top of a module, it'll probably sit there forever. Tools for removing unused
imports would help with that problem, but having the imports be local still
helps you reason about the imports for a section of code (and to an extent
removes the need for such a tool). And of course, if all of the imports that
a function uses are within its body, then removing the function removes all
of those imports without you having to even spend the time to figure out
what they were.
Arguably an even bigger benefit of local imports comes from conditional
compilation. When you have a template, static if block, or version statement
in your code, the code inside of it may or may not be compiled into your
program (depending on what your code is doing). So, by putting the imports
used within that code inside of that code, you can avoid having them be
imported at all if that code isn't actually compiled in (which is
particularly critical in the case of version statements that could use
platform-specific modules but helps with avoiding unnecessary compilation in
general).
The downside of course is that you then have import statements throughout
your code, and they're often going to be duplicated throughout a module (or
even within a function if you localize them far enough), because separate
parts of the code then need their own local imports. So, some folks think
that it's just simpler to throw the imports at the top of the module (and
particularly for small programs, it probably is).
Another issue is that local imports don't really work for stuff in function
signatures. For member functions, you can localize imports to the class or
struct, but for module-level imports, they have to go at the module level,
so they're not local. There was talk of adding a language feature to fix
that, but it never happened. However, we did at some point get a template to
do it for you. object.d contains imported, which allows you to do stuff like
auto foo(imported!"std.datetime".SysTime st) {...}
I'm not sure how much it's really used though. I suspect that it's ugly
enough that it's not used much, and I don't know if it's even very well
known at this point (personally, I keep forgetting that it was added).
However, it does have the benefit of making it so that removing the
parameter or return type using that template would remove the import, just
like removing a function removes any of its local imports in the process.
So, it's arguably a good idea, but personally, I find it ugly enough that I
don't use it.
Another thing to keep in mind (though it also affects module-level imports)
is that public, package, and private affect imports - even when used with :
or with {} - so if you use an access modifier in a way that affects an
import (e.g. if you put public: at the top of your class and then have
imports right under it), you can accidentally end up with imports that
aren't private. If you're in the habit of just slapping all of your imports
at the top of the module, then this is unlikely to be an issue, but if you
put them throughout the module (and not just within functions), then it
could bite you. So, you do need to be
Re: Help optimize D solution to phone encoding problem: extremely slow performace.
On Tuesday, 16 January 2024 at 16:56:04 UTC, Siarhei Siamashka wrote: On Tuesday, 16 January 2024 at 15:50:35 UTC, H. S. Teoh wrote: Unfortunately there seems to be some discrepancy between the output I got and the prescribed output in your repository. For example, in your output the number 1556/0 does not have an encoding, but isn't "1 Mai 0" a valid encoding according to your dictionary and the original problem description? You are not allowed to emit "1" as the first token in the output as long as there are any dictionary word matches at that position. The relevant paragraph from the problem statement: ==snip== Encodings of phone numbers can consist of a single word or of multiple words separated by spaces. The encodings are built word by word from left to right. If and only if at a particular point no word at all from the dictionary can be inserted, a single digit from the phone number can be copied to the encoding instead. Two subsequent digits are never allowed, though. To put it differently: In a partial encoding that currently covers k digits, digit k+1 is encoded by itself if and only if, first, digit k was not encoded by a digit and, second, there is no word in the dictionary that can be used in the encoding starting at digit k+1. ==snip== I also spent a bit of time trying to figure out this nuance when implementing my solution. It doesn't make much sense visually (no back-to-back digits in the output either way), but that's how it is. Exactly, this is one of the things that make this problem a bit annoying to solve :) @"H. S. Teoh" you implemented the solution as a Trie!! Nice, that's also what I did when I "participated" in the study. Here's [my Trie solution in Java](https://github.com/renatoathaydes/prechelt-phone-number-encoding/blob/fastest-implementations-print-or-count/src/java/Main.java). These are basically the two common approaches to the problem: a Trie or a numeric-based table. According to the study, people who use scripting languages almost always go with the numeric approach, while people coming from lower level languages tend to use a data structure like Trie (if they don't know Trie, they come up with something similar which is fascinating), which is harder to implement but more efficient in general. Can I ask you why didn't you use the [D stdlib Trie](https://dlang.org/phobos/std_uni.html#codepointTrie)? Not sure that would've worked, but did you consider that?
Re: Nested delegates and closure allocations
On Tuesday, 16 January 2024 at 15:39:07 UTC, Anonymouse wrote:
If I make a `scope` variable of the delegate and pass *it* to
`receiveTimeout`, there no longer seems to be any mention of
the closure in the error (given 2.092 or later).
```d
void foo(Thing thing) @nogc
{
void sendThing(const string where, int i)
{
send(thing, where, i);
}
scope scopeSendThing =
receiveTimeout(Duration.zero, scopeSendThing);
}
```
Ignoring that it doesn't compile for other reasons; provided
`scope scopeSendThing = ` compiles -- as in,
`` is eligible for `scope` -- is this a valid
workaround?
Correct. The problem is that `receiveTimeout` is defined as a
template variadic function: it *can* take a scoped function, but
it doesn't (can't) declare that its argument is always scoped, so
since scoped parameters are opt-in, it defaults to unscoped. And
has to also default to unscoped, because you can pass
unscoped values to scoped parameters but not the other way
around, so it defaults to the most generic type available. With
your scoped variable you provide DMD the critical hint that
actually you want the closure to be scoped, and once the value is
scoped it stays scoped.
Re: Help optimize D solution to phone encoding problem: extremely slow performace.
On Tuesday, 16 January 2024 at 15:50:35 UTC, H. S. Teoh wrote: Unfortunately there seems to be some discrepancy between the output I got and the prescribed output in your repository. For example, in your output the number 1556/0 does not have an encoding, but isn't "1 Mai 0" a valid encoding according to your dictionary and the original problem description? You are not allowed to emit "1" as the first token in the output as long as there are any dictionary word matches at that position. The relevant paragraph from the problem statement: ==snip== Encodings of phone numbers can consist of a single word or of multiple words separated by spaces. The encodings are built word by word from left to right. If and only if at a particular point no word at all from the dictionary can be inserted, a single digit from the phone number can be copied to the encoding instead. Two subsequent digits are never allowed, though. To put it differently: In a partial encoding that currently covers k digits, digit k+1 is encoded by itself if and only if, first, digit k was not encoded by a digit and, second, there is no word in the dictionary that can be used in the encoding starting at digit k+1. ==snip== I also spent a bit of time trying to figure out this nuance when implementing my solution. It doesn't make much sense visually (no back-to-back digits in the output either way), but that's how it is.
Re: Help optimize D solution to phone encoding problem: extremely slow performace.
P.S. Compiling my program with `ldc -O2`, it runs so fast that I couldn't measure any meaningful running time that's greater than startup overhead. So I wrote a helper program to generate random phone numbers up to 50 characters long, and found that it could encode 1 million phone numbers in 2.2 seconds (using the 75,000 entry dictionary from your repository). Counting vs. printing the results made no significant difference to this. T -- People tell me that I'm skeptical, but I don't believe them.
Re: Help optimize D solution to phone encoding problem: extremely slow performace.
On Tue, Jan 16, 2024 at 07:50:35AM -0800, H. S. Teoh via Digitalmars-d-learn
wrote:
[...]
> Unfortunately there seems to be some discrepancy between the output I
> got and the prescribed output in your repository. For example, in your
> output the number 1556/0 does not have an encoding, but isn't "1 Mai 0"
> a valid encoding according to your dictionary and the original problem
> description?
[...]
Also, found a bug in my program that misses some solutions when the
phone number has trailing non-digits. Here's the updated code. It still
finds extra encodings from the output in your repo, though. Maybe I
misunderstood part of the requirements?
--snip--
/**
* Encoding phone numbers according to a dictionary.
*/
import std;
/**
* Table of digit mappings.
*/
static immutable ubyte[dchar] digitOf;
shared static this()
{
digitOf = [
'E': 0,
'J': 1, 'N': 1, 'Q': 1,
'R': 2, 'W': 2, 'X': 2,
'D': 3, 'S': 3, 'Y': 3,
'F': 4, 'T': 4,
'A': 5, 'M': 5,
'C': 6, 'I': 6, 'V': 6,
'B': 7, 'K': 7, 'U': 7,
'L': 8, 'O': 8, 'P': 8,
'G': 9, 'H': 9, 'Z': 9,
];
}
/**
* Trie for storing dictionary words according to the phone number mapping.
*/
class Trie
{
Trie[10] edges;
string[] words;
private void insert(string word, string suffix)
{
const(ubyte)* dig;
while (!suffix.empty &&
(dig = std.ascii.toUpper(suffix[0]) in digitOf) is null)
{
suffix = suffix[1 .. $];
}
if (suffix.empty)
{
words ~= word;
return;
}
auto node = new Trie;
auto idx = *dig;
if (edges[idx] is null)
{
edges[idx] = new Trie;
}
edges[idx].insert(word, suffix[1 .. $]);
}
/**
* Insert a word into the Trie.
*
* Characters that don't map to any digit are ignored in building the Trie.
* However, the original form of the word will be retained as-is in the
* leaf node.
*/
void insert(string word)
{
insert(word, word[]);
}
/**
* Iterate over all words stored in this Trie.
*/
void foreachEntry(void delegate(string path, string word) cb)
{
void impl(Trie node, string path = "")
{
if (node is null) return;
foreach (word; node.words)
{
cb(path, word);
}
foreach (i, child; node.edges)
{
impl(child, path ~ cast(char)('0' + i));
}
}
impl(this);
}
}
/**
* Loads the given dictionary into a Trie.
*/
Trie loadDictionary(R)(R lines)
if (isInputRange!R & is(ElementType!R : const(char)[]))
{
Trie result = new Trie;
foreach (line; lines)
{
result.insert(line.idup);
}
return result;
}
///
unittest
{
auto dict = loadDictionary(q"ENDDICT
an
blau
Bo"
Boot
bo"s
da
Fee
fern
Fest
fort
je
jemand
mir
Mix
Mixer
Name
neu
o"d
Ort
so
Tor
Torf
Wasser
ENDDICT".splitLines);
auto app = appender!(string[]);
dict.foreachEntry((path, word) { app ~= format("%s: %s", path, word); });
assert(app.data == [
"10: je",
"105513: jemand",
"107: neu",
"1550: Name",
"253302: Wasser",
"35: da",
"38: so",
"400: Fee",
"4021: fern",
"4034: Fest",
"482: Tor",
"4824: fort",
"4824: Torf",
"51: an",
"562: mir",
"562: Mix",
"56202: Mixer",
"78: Bo\"",
"783: bo\"s",
"7857: blau",
"7884: Boot",
"824: Ort",
"83: o\"d"
]);
}
/**
* Find all encodings of the given phoneNumber according to the given
* dictionary, and write each encoding to the given sink.
*/
void findMatches(W)(Trie dict, const(char)[] phoneNumber, W sink)
if (isOutputRange!(W, string))
{
bool impl(Trie node, const(char)[] suffix, string[] path, bool allowDigit)
{
if (node is null)
return false;
// Ignore non-digit characters in phone number
while (!suffix.empty && (suffix[0] < '0' || suffix[0] > '9'))
suffix = suffix[1 .. $];
if (suffix.empty)
{
// Found a match, print result
foreach (word; node.words)
{
put(sink, format("%s: %-(%s %)", phoneNumber,
path.chain(only(word;
}
return !node.words.empty;
}
bool ret;
foreach (word; node.words)
{
// Found a matching word, try to match the rest of the phone
// number.
if (impl(dict, suffix, path ~ word, true))
{
allowDigit = false;
ret = true;
}
}
if (impl(node.edges[suffix[0] -
Re: Help optimize D solution to phone encoding problem: extremely slow performace.
On Mon, Jan 15, 2024 at 08:10:55PM +, Renato via Digitalmars-d-learn wrote:
> On Monday, 15 January 2024 at 01:10:14 UTC, Sergey wrote:
> > On Sunday, 14 January 2024 at 17:11:27 UTC, Renato wrote:
> > > If anyone can find any flaw in my methodology or optmise my code so
> > > that it can still get a couple of times faster, approaching Rust's
> > > performance, I would greatly appreciate that! But for now, my
> > > understanding is that the most promising way to get there would be
> > > to write D in `betterC` style?!
> >
> > I've added port from Rust in the PR comment. Can you please check
> > this solution?
> > Most probably it need to be optimized with profiler. Just
> > interesting how close-enough port will work.
>
> As discussed on GitHub, the line-by-line port of the Rust code is 5x
> slower than [my latest solution using
> int128](https://github.com/renatoathaydes/prechelt-phone-number-encoding/blob/0cbfd41a072718bfb0c0d0af8bb7266471e7e94c/src/d/src/dencoder.d),
> which is itself 3 to 4x slower than the Rust implementation (at around
> the same order of magnitude as algorithm-equivalent Java and Common
> Lisp implementations, D is perhaps 15% faster).
>
> I did the best I could to make D run faster, but we hit a limit that's
> a bit hard to get past now. Happy to be given suggestions (see
> profiling information in previous messages), but I've run out of ideas
> myself.
This problem piqued my interest, so yesterday and today I worked on it
and came up with my own solution (I did not look at existing solutions
in order to prevent bias). I have not profiled it or anything, but the
runtime seems quite promising.
Here it is:
-snip--
/**
* Encoding phone numbers according to a dictionary.
*/
import std;
/**
* Table of digit mappings.
*/
static immutable ubyte[dchar] digitOf;
shared static this()
{
digitOf = [
'E': 0,
'J': 1, 'N': 1, 'Q': 1,
'R': 2, 'W': 2, 'X': 2,
'D': 3, 'S': 3, 'Y': 3,
'F': 4, 'T': 4,
'A': 5, 'M': 5,
'C': 6, 'I': 6, 'V': 6,
'B': 7, 'K': 7, 'U': 7,
'L': 8, 'O': 8, 'P': 8,
'G': 9, 'H': 9, 'Z': 9,
];
}
/**
* Trie for storing dictionary words according to the phone number mapping.
*/
class Trie
{
Trie[10] edges;
string[] words;
private void insert(string word, string suffix)
{
const(ubyte)* dig;
while (!suffix.empty &&
(dig = std.ascii.toUpper(suffix[0]) in digitOf) is null)
{
suffix = suffix[1 .. $];
}
if (suffix.empty)
{
words ~= word;
return;
}
auto node = new Trie;
auto idx = *dig;
if (edges[idx] is null)
{
edges[idx] = new Trie;
}
edges[idx].insert(word, suffix[1 .. $]);
}
/**
* Insert a word into the Trie.
*
* Characters that don't map to any digit are ignored in building the Trie.
* However, the original form of the word will be retained as-is in the
* leaf node.
*/
void insert(string word)
{
insert(word, word[]);
}
/**
* Iterate over all words stored in this Trie.
*/
void foreachEntry(void delegate(string path, string word) cb)
{
void impl(Trie node, string path = "")
{
if (node is null) return;
foreach (word; node.words)
{
cb(path, word);
}
foreach (i, child; node.edges)
{
impl(child, path ~ cast(char)('0' + i));
}
}
impl(this);
}
}
/**
* Loads the given dictionary into a Trie.
*/
Trie loadDictionary(R)(R lines)
if (isInputRange!R & is(ElementType!R : const(char)[]))
{
Trie result = new Trie;
foreach (line; lines)
{
result.insert(line.idup);
}
return result;
}
///
unittest
{
auto dict = loadDictionary(q"ENDDICT
an
blau
Bo"
Boot
bo"s
da
Fee
fern
Fest
fort
je
jemand
mir
Mix
Mixer
Name
neu
o"d
Ort
so
Tor
Torf
Wasser
ENDDICT".splitLines);
auto app = appender!(string[]);
dict.foreachEntry((path, word) { app ~= format("%s: %s", path, word); });
assert(app.data == [
"10: je",
"105513: jemand",
"107: neu",
"1550: Name",
"253302: Wasser",
"35: da",
"38: so",
"400: Fee",
"4021: fern",
"4034: Fest",
"482: Tor",
"4824: fort",
"4824: Torf",
"51: an",
"562: mir",
"562: Mix",
"56202: Mixer",
"78: Bo\"",
"783: bo\"s",
"7857: blau",
"7884: Boot",
"824: Ort",
"83: o\"d"
]);
}
/**
* Find all encodings of the given phoneNumber according to the given
* dictionary, and write each encoding to the given sink.
*/
void findMatches(W)(Trie dict, const(char)[] phoneNumber, W sink)
Re: Nested delegates and closure allocations
On Tuesday, 16 January 2024 at 13:45:22 UTC, FeepingCreature
wrote:
Am I safe as long as I don't do something like, pass
`` as an argument to `std.concurrency.receive`?
Yes.
Thank you.
And to make sure I don't misunderstand the spec; in the case I
*do* have a delegate I want to pass elsewhere, and `scope dg =
` *does* compile, passing that `dg` around won't allocate
a closure?
```d
void foo(Thing thing) @nogc
{
void sendThing(const string where, int i)
{
send(thing, where, i);
}
receiveTimeout(Duration.zero, );
}
```
The above naturally won't compile because
`std.concurrency.receiveTimeout` requires the garbage collector,
but notably in the error message, this is included;
```
onlineapp.d(10): Error: function `onlineapp.foo` is `@nogc` yet
allocates closure for `foo()` with the GC
onlineapp.d(12):`onlineapp.foo.sendThing` closes over
variable `thing` at onlineapp.d(10)
```
If I make a `scope` variable of the delegate and pass *it* to
`receiveTimeout`, there no longer seems to be any mention of the
closure in the error (given 2.092 or later).
```d
void foo(Thing thing) @nogc
{
void sendThing(const string where, int i)
{
send(thing, where, i);
}
scope scopeSendThing =
receiveTimeout(Duration.zero, scopeSendThing);
}
```
Ignoring that it doesn't compile for other reasons; provided
`scope scopeSendThing = ` compiles -- as in,
`` is eligible for `scope` -- is this a valid
workaround?
Re: Understanding the Use of Nested Import and Selective Import in D
On Tuesday, 16 January 2024 at 13:19:59 UTC, Orfeo wrote: I found myself a bit perplexed when it comes to the usage of "nested imports" and selective imports. It seems that prominent D programmers have varied opinions on the matter. I would love to hear your insights and experiences on this topic. [...] see also [Workaround for DIP 1005](http://forum.dlang.org/post/tzqzmqhankrkbrfsr...@forum.dlang.org)
Re: Nested delegates and closure allocations
On Tuesday, 16 January 2024 at 10:56:58 UTC, Anonymouse wrote:
I'm increasingly using nested delegates to partition code.
```d
void foo(Thing thing)
{
void sendThing(const string where, int i)
{
send(thing, where, i);
}
sendThing("bar", 42);
}
```
...
3. Those referenced stack variables that make up the closure
are allocated on the GC heap, unless:
* The closure is passed to a scope parameter.
* The closure is an initializer for a scope variable.
* The closure is assigned to a scope variable.
I'm generally not storing the delegates or passing them around
as values, so I don't think the thing about scope variables and
parameters *directly* applies.
Am I safe as long as I don't do something like, pass
`` as an argument to `std.concurrency.receive`?
Yes.
Re: Understanding the Use of Nested Import and Selective Import in D
On Tuesday, 16 January 2024 at 13:37:59 UTC, user1234 wrote: Implementation detail. D frontend resolves identifiers using associative arrays (that's called symtabs in the compiler IIRC), hence the only complexity is the scope (plus the import decls found while going back to the module scope). oops forgot to say: so it's fast.
Re: Understanding the Use of Nested Import and Selective Import in D
On Tuesday, 16 January 2024 at 13:19:59 UTC, Orfeo wrote: I found myself a bit perplexed when it comes to the usage of "nested imports" and selective imports. It seems that prominent D programmers have varied opinions on the matter. I would love to hear your insights and experiences on this topic. Here's a quick summary of what I've come across from three influential D programmers: - Adam Ruppe: In his blog post titled [D's selective imports have effects you may not want](http://dpldocs.info/this-week-in-arsd/Blog.Posted_2023_11_06.html) have effects you may not want, Adam advises against the use of selective imports. He highlights potential unwanted side effects and suggests caution when employing them. - Atila Neves: At DConf 2023, Atila Neves recommended the use of nested imports. He argues that nested imports can make refactoring easier and help in assessing the dependencies a function has. - Rober Schadek: Also at DConf 2023, Rober Schadek discouraged the use of nested imports, taking a stance different from Atila Neves. Now, the big question is: What's your preferred approach? Another point is that the use of selective imports tends to be "a refactoring". You start with a global or local import. Once everything is fine you'll think that's it's a good idea to make the import selective, i.e "because I only use that in there". Problem is, if someone else at some point work on your code: 1. he needs to add more to the selection 2. completion may not work anymore (will only show what's selected) So it's a bit a thing of expert. Given these arguments I think that global imports should not be selective, only local ones should. Implementation detail. D frontend resolves identifiers using associative arrays (that's called symtabs in the compiler IIRC), hence the only complexity is the scope (plus the import decls found while going back to the module scope).
Re: Understanding the Use of Nested Import and Selective Import in D
Yes, I try to place my imports at the most general location that makes sense. Sometimes that is at the module level, other times its in a single function. Or anywhere in between (such as a struct).
Understanding the Use of Nested Import and Selective Import in D
I found myself a bit perplexed when it comes to the usage of "nested imports" and selective imports. It seems that prominent D programmers have varied opinions on the matter. I would love to hear your insights and experiences on this topic. Here's a quick summary of what I've come across from three influential D programmers: - Adam Ruppe: In his blog post titled [D's selective imports have effects you may not want](http://dpldocs.info/this-week-in-arsd/Blog.Posted_2023_11_06.html) have effects you may not want, Adam advises against the use of selective imports. He highlights potential unwanted side effects and suggests caution when employing them. - Atila Neves: At DConf 2023, Atila Neves recommended the use of nested imports. He argues that nested imports can make refactoring easier and help in assessing the dependencies a function has. - Rober Schadek: Also at DConf 2023, Rober Schadek discouraged the use of nested imports, taking a stance different from Atila Neves. Now, the big question is: What's your preferred approach?
Nested delegates and closure allocations
I'm increasingly using nested delegates to partition code.
```d
void foo(Thing thing)
{
void sendThing(const string where, int i)
{
send(thing, where, i);
}
sendThing("bar", 42);
}
```
...where the nested `sendThing` sometimes returns something,
sometimes doesn't. `Thing` may be a class or a value type,
`thing` may be a parameter to the parent function, may be a
variable previously declared in the parent function, may be
mutable or immutable, may be modified inside `sendThing`; any
combination of things. If `sendThing` doesn't need to access the
scope of `foo` I mark it `static` to enforce that, but mostly it
does.
From the spec:
### `19.19.2` Delegates & Closures
3. Those referenced stack variables that make up the closure
are allocated on the GC heap, unless:
* The closure is passed to a scope parameter.
* The closure is an initializer for a scope variable.
* The closure is assigned to a scope variable.
I'm generally not storing the delegates or passing them around as
values, so I don't think the thing about scope variables and
parameters *directly* applies.
Am I safe as long as I don't do something like, pass ``
as an argument to `std.concurrency.receive`?
Re: `static` function ... cannot access variable in frame of ...
On Monday, 15 January 2024 at 23:06:00 UTC, Steven Schveighoffer
wrote:
As a workaround, you can alias the outer function in the struct:
```d
struct S
{
alias foo = S_foo;
}
```
This might be less than ideal, but at least it works.
It does! And it's good enough for me. Thanks a lot!
-- Bastiaan.
