Re: Increasing D Compiler Speed by Over 75%
Am 25.07.2013 20:03, schrieb Walter Bright: http://www.reddit.com/r/programming/comments/1j1i30/increasing_the_d_compiler_speed_by_over_75/ do you compare dmc based and visualc based dmd builds? the vc dmd build seems to be always two times faster - how does that look with your optimization?
Re: Increasing D Compiler Speed by Over 75%
On Thursday, 25 July 2013 at 18:03:22 UTC, Walter Bright wrote: http://www.reddit.com/r/programming/comments/1j1i30/increasing_the_d_compiler_speed_by_over_75/ I just reported this compile speed killer: http://d.puremagic.com/issues/show_bug.cgi?id=10716 It has a big impact on some of the tests in the DMD test suite. It might also be responsible for a significant part of the compilation time of Phobos, since array literals tend to be widely used inside unittest functions.
Re: Article: Increasing the D Compiler Speed by Over 75%
Walter Bright: Hash collisions are not the problem - I sized the hash bucket array to make it fairly sparse. Neither is the hash algorithm. The slowness was in the frackin' convert the hash to an index in the bucket, which is a modulus operation. Thankfully in that thread Paul Hsieh has given more precise suggestions, he's kind of expert on such matters. Bye, bearophile
Re: Article: Increasing the D Compiler Speed by Over 75%
26-Jul-2013 01:25, Walter Bright пишет: On 7/25/2013 1:00 PM, bearophile wrote: Walter Bright: It's not the hashing that's slow. It's the lookup that is. By different hashing scheme I meant different strategies in resolving hash collisions, likes double hashing, internal hashing, cuckoo hashing, and so on and on. Maybe one of such alternative strategies is more fit for the needs of dmd compilation. (I think that currently the Python dicts are using a hashing strategy different from the built-in dictionaries of D. The Python style of hashing was implemented in D some months ago, but I don't remember what happened to that project later). Hash collisions are not the problem - I sized the hash bucket array to make it fairly sparse. Neither is the hash algorithm. The slowness was in the frackin' convert the hash to an index in the bucket, which is a modulus operation. Then it's past due to finally stop the madness of modulo prime table and use a power of 2 size. In essence what modulo prime does is simply enhancing the quality of your hash function w.r.t. collisions (it helps to distribute values more evenly). Any of new decent hashes are good enough to work with plain slice the lower bits approach. Also, computing the hash is done exactly once, in the lexer. All the more reason to use good hash function and kill the modulo prime. Thereafter, all identifiers are known only by their handles, which are (not coincidentally) the pointer to the identifier, and by its very nature is unique. -- Dmitry Olshansky
Re: Article: Increasing the D Compiler Speed by Over 75%
26-Jul-2013 14:47, Dmitry Olshansky пишет: 26-Jul-2013 01:25, Walter Bright пишет: The slowness was in the frackin' convert the hash to an index in the bucket, which is a modulus operation. Then it's past due to finally stop the madness of modulo prime table and use a power of 2 size. In essence what modulo prime does is simply enhancing the quality of your hash function w.r.t. collisions (it helps to distribute values more evenly). Any of new decent hashes are good enough to work with plain slice the lower bits approach. To be more concrete: Spooky hash http://burtleburtle.net/bob/hash/spooky.html (Public domain) S-box hash http://home.comcast.net/~bretm/hash/10.html (Published paper) Or even a good ol' FNV (Public domain) http://isthe.com/chongo/tech/comp/fnv/#FNV-1a -- Dmitry Olshansky
Re: Increasing D Compiler Speed by Over 75%
On 7/26/2013 1:25 AM, dennis luehring wrote: do you compare dmc based and visualc based dmd builds? the vc dmd build seems to be always two times faster - how does that look with your optimization? It would be most interesting to see just what it was that made the vc build faster. But that won't help on Linux/FreeBSD/OSX.
Re: Article: Increasing the D Compiler Speed by Over 75%
On 7/26/2013 5:11 AM, Dmitry Olshansky wrote: 26-Jul-2013 14:47, Dmitry Olshansky пишет: 26-Jul-2013 01:25, Walter Bright пишет: The slowness was in the frackin' convert the hash to an index in the bucket, which is a modulus operation. Then it's past due to finally stop the madness of modulo prime table and use a power of 2 size. In essence what modulo prime does is simply enhancing the quality of your hash function w.r.t. collisions (it helps to distribute values more evenly). Any of new decent hashes are good enough to work with plain slice the lower bits approach. To be more concrete: Spooky hash http://burtleburtle.net/bob/hash/spooky.html (Public domain) S-box hash http://home.comcast.net/~bretm/hash/10.html (Published paper) Or even a good ol' FNV (Public domain) http://isthe.com/chongo/tech/comp/fnv/#FNV-1a How about a pull request so we can try it out?
Re: Article: Increasing the D Compiler Speed by Over 75%
26-Jul-2013 23:17, Walter Bright пишет: On 7/26/2013 5:11 AM, Dmitry Olshansky wrote: 26-Jul-2013 14:47, Dmitry Olshansky пишет: 26-Jul-2013 01:25, Walter Bright пишет: The slowness was in the frackin' convert the hash to an index in the bucket, which is a modulus operation. Then it's past due to finally stop the madness of modulo prime table and use a power of 2 size. In essence what modulo prime does is simply enhancing the quality of your hash function w.r.t. collisions (it helps to distribute values more evenly). Any of new decent hashes are good enough to work with plain slice the lower bits approach. To be more concrete: Spooky hash http://burtleburtle.net/bob/hash/spooky.html (Public domain) S-box hash http://home.comcast.net/~bretm/hash/10.html (Published paper) Or even a good ol' FNV (Public domain) http://isthe.com/chongo/tech/comp/fnv/#FNV-1a How about a pull request so we can try it out? Thought as much. I'll be away at the weekends but I'll surely try my hand at it afterwards. -- Dmitry Olshansky
Re: echo: -n, the next installment
On Friday, 26 July 2013 at 00:38:46 UTC, John Colvin wrote: After a few weeks of not getting around to it, here's my second post: http://foreach-hour-life.blogspot.co.uk/2013/07/the-first-corner-n-for-echo.html BTW, std.getopt is a good way to parse arguments. Not sure if it is relevant to what you want to teach, but should generally be preferred over handwritten.
