www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Arrays template arguments and CT data structures

reply bearophile <bearophileHUGS lycos.com> writes:
(after a small discussion on IRC) Tuples may be used for similar purposes, but
fixed-sized arrays are simpler to use, simpler to define, and they don't induce
compilation/code bloat. Is this a good idea?

int foo(int[3] arr)() {
    return arr[1];
}
const int[3] a = [10, 20, 30];
void main() {
    foo!(a)(); // a must be a constant fixed-sized array
}

--------------

Related:
A good purpose for compile-time functions is to pre-generate constant data
structures, avoiding to waste time generating them at compile time. But
currently creating fixed-sized arrays at compile time while possible is tricky
(it's easy for me to write code that doesn't compile. So I'd like D2 to become
more flexible here).
Constant associative arrays defined at compile time may use perfect hashing
functions that can be used at run time.
And generating structures with pointers is not possible at compile time
(possible usage for such structure: a trie that stores a constant dictionary,
avoiding both build and load time, even if loading the precomputed chunk of
memory of the array at run time takes a short time). At compile time indexes
can be used instead of pointers, for example allocating the trie nodes into a
compile time array and then using indexes to link nodes together.

Bye,
bearophile
Oct 02 2009
next sibling parent reply language_fan <foo bar.com.invalid> writes:
Fri, 02 Oct 2009 16:56:48 -0400, bearophile thusly wrote:

 A good purpose for compile-time functions is to pre-generate constant
 data structures, avoiding to waste time generating them at compile time.
 But currently creating fixed-sized arrays at compile time while possible
 is tricky (it's easy for me to write code that doesn't compile. So I'd
 like D2 to become more flexible here). Constant associative arrays
 defined at compile time may use perfect hashing functions that can be
 used at run time. And generating structures with pointers is not
 possible at compile time (possible usage for such structure: a trie that
 stores a constant dictionary, avoiding both build and load time, even if
 loading the precomputed chunk of memory of the array at run time takes a
 short time). At compile time indexes can be used instead of pointers,
 for example allocating the trie nodes into a compile time array and then
 using indexes to link nodes together.

You have probably already noticed that there is always a tradeoff to be made. Either you get smaller binaries and faster compilation times or larger binaries and (perhaps) more efficient runtime performance. Note that if the data structures are small, generating them takes very little time on modern 32/64-bit hardware. OTOH if you have tens of megabytes of binary data in your .exe, hard drives are a serious bottleneck.
Oct 02 2009
next sibling parent bearophile <bearophileHUGS lycos.com> writes:
language_fan:

 Note 
 that if the data structures are small, generating them takes very little 
 time on modern 32/64-bit hardware. OTOH if you have tens of megabytes of 
 binary data in your .exe, hard drives are a serious bottleneck.

You forget an important thing: If you generate things at compile time the compiler is more able to optimize the code, because more data is available at compile time (it can be a form of "partial specialization"). --------------------- Tom S:
 What do you mean by that? So parametrizing a template with a static 
 array would cause less bloat than doing so with a tuple? I guess you 
 might shave off a few bytes if mangling was shorter, but except that? *gasp*

Tuples seems composed of dynamically typed items at compile time, so an array may need less memory to be managed by the compiler because its items have all the same type. And regarding the binary bloat, I was thinking about the "static foreach" over tuples, that has inflated some of my programs. But this isn't a real problem, so please breath normally :-) Bye and thank you, bearophile
Oct 02 2009
prev sibling parent BCS <none anon.com> writes:
Hello language_fan,

 You have probably already noticed that there is always a tradeoff to
 be made. Either you get smaller binaries and faster compilation times
 or larger binaries and (perhaps) more efficient runtime performance.
 Note that if the data structures are small, generating them takes very
 little time on modern 32/64-bit hardware. OTOH if you have tens of
 megabytes of binary data in your .exe, hard drives are a serious
 bottleneck.
 

If the data is setup correctly (e.i. not mixed in with other stuff) then the only the data that is called for will be paged in. I'm having a hard time thinking of a situation where this would be less than ideal. The only case I can think of is where the data can be compressed a lot and you page in compressed structures and then expand as needed into memory. Most simple systems would read in the same data in a (probably bulkier format) but do it all before the first access.
Oct 03 2009
prev sibling parent Tom S <h3r3tic remove.mat.uni.torun.pl> writes:
bearophile wrote:
 (after a small discussion on IRC) Tuples may be used for similar purposes, but
fixed-sized arrays are simpler to use, simpler to define, and they don't induce
compilation/code bloat. (...)

What do you mean by that? So parametrizing a template with a static array would cause less bloat than doing so with a tuple? I guess you might shave off a few bytes if mangling was shorter, but except that? *gasp* -- Tomasz Stachowiak http://h3.team0xf.com/ h3/h3r3tic on #D freenode
Oct 02 2009