Re: CTFE question
On Mon, Sep 3, 2012 at 4:08 PM, bearophile wrote: >> Worth a bug report? > > > Yeah. CTFE must give the same results when CTFE works. http://d.puremagic.com/issues/show_bug.cgi?id=8614
Re: CTFE question
Philippe Sigaud: Worth a bug report? Yeah. CTFE must give the same results when CTFE works. A simpler test case for Bugzilla: import std.stdio; int[] foo(int[] data) { foreach (i, ref x; data) { x++; i++; } return data; } void main() { enum result1 = foo([10, 20, 30, 40]); auto result2 = foo([10, 20, 30, 40]); writeln(result1); // [11, 21, 31, 41] writeln(result2); // [11, 20, 31, 40] } Bye, bearophile
Re: CTFE question
On Mon, Sep 3, 2012 at 1:27 PM, Don Clugston wrote: >> Godd adivce, except beware of using ++ and --, they don't work at >> compile-time. I'm regularly caught unaware by this, particularly while >> looping. > > > Really? That's scary. Is there a bug report for this? I re-tried this and I was mistaken: it's not ++ or --, it's changing an iteration index at compile-time. My bad. int[] indices(string s) { int[] store; foreach(i,ch; s[0..$-1]) { store ~= i; if (s[i..i+2] == "aa") i += 1; // also ++i or i++, no difference here } return store; } void main() { enum result1 = indices("aaabc"); auto result2 = indices("aaabc"); writeln(result1); // [0,1,2,3] writeln(result2); // [0,2,3] } I know changing 'i' while iterating is not a good idea, but at least in this case, CT-executed and RT-execution give a different result. All my other tests with ++ and -- give correct results, sorry for the bad publicity. Worth a bug report?
Re: CTFE question
On 28/08/12 19:40, Philippe Sigaud wrote: On Tue, Aug 28, 2012 at 2:07 PM, Chris Cain wrote: On Tuesday, 28 August 2012 at 11:39:20 UTC, Danny Arends wrote: Ahhh I understand... As a follow up, is it then possible to 'track' filling a large enum / immutable on compile time by outputting a msg every for ? I'm generating rotation matrices for yaw, pitch and roll at compile time which can take a long time depending on how fine grained I create them. I'm pretty sure there isn't. However, if you're just trying to develop/test your algorithm, you could write a program that runs it as a normal function (and just use writeln) as you develop it. After it's done, you remove the writelns, mark the function as pure and it should work exactly the same in CTFE. Godd adivce, except beware of using ++ and --, they don't work at compile-time. I'm regularly caught unaware by this, particularly while looping. Really? That's scary. Is there a bug report for this?
Re: CTFE question
On Tue, Aug 28, 2012 at 2:07 PM, Chris Cain wrote: > On Tuesday, 28 August 2012 at 11:39:20 UTC, Danny Arends wrote: >> >> Ahhh I understand... >> >> As a follow up, is it then possible to 'track' filling a >> large enum / immutable on compile time by outputting a msg >> every for ? >> >> I'm generating rotation matrices for yaw, pitch and roll >> at compile time which can take a long time depending on >> how fine grained I create them. > > > I'm pretty sure there isn't. However, if you're just trying to develop/test > your algorithm, you could write a program that runs it as a normal function > (and just use writeln) as you develop it. After it's done, you remove the > writelns, mark the function as pure and it should work exactly the same in > CTFE. Godd adivce, except beware of using ++ and --, they don't work at compile-time. I'm regularly caught unaware by this, particularly while looping. Danny is also using 0..360, which is a runtime value. There exists a compile-time version of foreach which is automatically invoked whenever you use foreach on a compile-time 'range' (aka, typetuple) So: template Loop(T...) { /* some code */ foreach(i,Type; T) pragma(msg, i); } will work. So, a way to get what the OP wanted is to create a tuple of the required length. Since integers are valid template arguments, we can use them directly like this: template staticRange(uint upto) { static if (upto == 0) alias TypeTuple!() staticRange; else alias TypeTuple!(staticRange!(upto-1), upto-1) staticRange; } So staticRange!3 is the tuple 0,1,2. (staticRange!0 is empty) You can foreach on it: pure int[] testCTFE(){ int[] r; pragma(msg, "Testing CTFE"); foreach(i; staticRange!360){ r ~= i; pragma(msg, i); } pragma(msg, "Done CTFE test"); return r; } Of course, that means knowing the upper value at compile-time.
Re: CTFE question
Danny Arends: Seems a bit strange that a discussion about yes/no newline is keeping this from getting into DMD. The ending newline is bad, because it unnecessarily kills some use cases for this feature. But I think the newline is not what is keeping it out of DMD. It's just there are about a hundred open patches, and Walter is currently implementing 64bits on Windows. Bye, bearophile
Re: CTFE question
On Tuesday, 28 August 2012 at 12:07:07 UTC, Chris Cain wrote: On Tuesday, 28 August 2012 at 11:39:20 UTC, Danny Arends wrote: I'm pretty sure there isn't. However, if you're just trying to develop/test your algorithm, you could write a program that runs it as a normal function (and just use writeln) as you develop it. After it's done, you remove the writelns, mark the function as pure and it should work exactly the same in CTFE. Well it just seems some compilation runs take way longer (and more memory) then others..Googling I found that I just got to wait for: https://github.com/D-Programming-Language/dmd/pull/692 to be accepted. Seems a bit strange that a discussion about yes/no newline is keeping this from getting into DMD. Just basic ctfewrite support would help me a lot. Gr, Danny Arends
Re: CTFE question
On Tuesday, 28 August 2012 at 11:39:20 UTC, Danny Arends wrote: Ahhh I understand... As a follow up, is it then possible to 'track' filling a large enum / immutable on compile time by outputting a msg every for ? I'm generating rotation matrices for yaw, pitch and roll at compile time which can take a long time depending on how fine grained I create them. I'm pretty sure there isn't. However, if you're just trying to develop/test your algorithm, you could write a program that runs it as a normal function (and just use writeln) as you develop it. After it's done, you remove the writelns, mark the function as pure and it should work exactly the same in CTFE.
Re: CTFE question
Ahhh I understand... As a follow up, is it then possible to 'track' filling a large enum / immutable on compile time by outputting a msg every for ? I'm generating rotation matrices for yaw, pitch and roll at compile time which can take a long time depending on how fine grained I create them. Gr, Danny Arends http://www.dannyarends.nl On Tuesday, 28 August 2012 at 11:29:32 UTC, Chris Cain wrote: On Tuesday, 28 August 2012 at 11:13:40 UTC, Danny Arends wrote: Is this a bug or am I doing something wrong ?? Danny Arends http://www.dannyarends.nl You're doing something wrong, but I can see why the error message would confuse you. Your problem is using those pragma(msg, ...) lines... They produce a message while something is being compiled, right? The CTFE function is ran _after_ it has been compiled. Hence i can't be read while the CTFE function is compiled. So, to be clear, doing this: - import std.stdio; import std.metastrings; pure int[] testCTFE(){ int[] r; pragma(msg, "Testing CTFE"); foreach(i; 0 .. 360){ r ~= i; //pragma(msg, Format!("Loop: %d",i)); } pragma(msg, "Done CTFE test"); return r; } immutable CTFEdata = testCTFE(); immutable CTFEdata2 = testCTFE(); void main(string[] args){ } Produces just one output: Testing CTFE Done CTFE test Because the pragmas are done _as it's compiled_, not as it's ran (even though CTFE is done "at compile time").
Re: CTFE question
On Tuesday, 28 August 2012 at 11:13:40 UTC, Danny Arends wrote: Is this a bug or am I doing something wrong ?? Danny Arends http://www.dannyarends.nl You're doing something wrong, but I can see why the error message would confuse you. Your problem is using those pragma(msg, ...) lines... They produce a message while something is being compiled, right? The CTFE function is ran _after_ it has been compiled. Hence i can't be read while the CTFE function is compiled. So, to be clear, doing this: - import std.stdio; import std.metastrings; pure int[] testCTFE(){ int[] r; pragma(msg, "Testing CTFE"); foreach(i; 0 .. 360){ r ~= i; //pragma(msg, Format!("Loop: %d",i)); } pragma(msg, "Done CTFE test"); return r; } immutable CTFEdata = testCTFE(); immutable CTFEdata2 = testCTFE(); void main(string[] args){ } Produces just one output: Testing CTFE Done CTFE test Because the pragmas are done _as it's compiled_, not as it's ran (even though CTFE is done "at compile time").
CTFE question
I have the following code: import std.stdio; import std.metastrings; pure int[] testCTFE(){ int[] r; pragma(msg, "Testing CTFE"); foreach(i; 0 .. 360){ r ~= i; pragma(msg, Format!("Loop: %d",i)); } pragma(msg, "Done CTFE test"); return r; } immutable CTFEdata = testCTFE(); void main(string[] args){ } -- I expected this would compile and during compilation print: Loop: 1 Loop:2, etc However, I get a compilation error: ctfe.d(9): Error: variable i cannot be read at compile time Is this a bug or am I doing something wrong ?? Danny Arends http://www.dannyarends.nl
Re: speeding up + ctfe question
I didn't use divisions or remainders, only multiplications. I've changed it so it only uses addition and now it still doesn't outperform a version that only checks odd's. it's not as fast as your version where every index corresponds to i*2+1 because I fill every even number with false...
Re: speeding up + ctfe question
I tried using 6k+-1 for all primes and for some reason it performed slower. I think I have something completely inefficient somewhere, can't figure out where though. You aren't, by any chance, using divisions or remainders? those are much slower than, say, multiplications (unless the divisor is a power of two and known at compile time, in which case the compiler will optimize them to bitwise operations). and I haven't tried with optimization on, first I want to get the algorithm as good as possible before trying to squeeze out those extra milliseconds :) I prefer to compile with optimizations on when trying to optimize something. That way I don't waste my time on micro-optimizations that the compiler could do for me.
Re: speeding up + ctfe question
I tried using 6k+-1 for all primes and for some reason it performed slower. I think I have something completely inefficient somewhere, can't figure out where though. I think it has something to do with me increasing k and then multiplying with k while I could have simply added 6 to K... and I haven't tried with optimization on, first I want to get the algorithm as good as possible before trying to squeeze out those extra milliseconds :)
Re: speeding up + ctfe question
On Sunday, 27 May 2012 at 17:00:01 UTC, maarten van damme wrote: ok, can't seem to reproduce the crashing. now on to optimizing my sieve a bit more ,9 miliseconds for 1_000_000 is still to slow. -- Er is zon buiten. Zonnige zondag namiddag met priemgetallen in de plaats van buiten zitten. Tss tss. :-) hoe? wie? x) Have you tried turning optimization on? I get about 8ms with your code with no flags and about 2.9 with -O -inline -release. To optimize it further you could make a sieve that only works with odd numbers. I get (https://gist.github.com/2817289) about 1ms that way. I'm sure it is possible to do much better, but that would probably be much more work too.
Re: speeding up + ctfe question
ok, can't seem to reproduce the crashing. now on to optimizing my sieve a bit more ,9 miliseconds for 1_000_000 is still to slow. -- Er is zon buiten. Zonnige zondag namiddag met priemgetallen in de plaats van buiten zitten. Tss tss. :-) hoe? wie? x)
Re: speeding up + ctfe question
I ran in two problems. It was extremely fast when sieving a byte array of 1 million entries (without optimizations at all) but when trying with 10_000_000 entries the program crashes before it even starts to execute (main isn't reached). You say it does compile, but then crashes immediatly? I can't reproduce that. For me it is a compile time error if toSieve is 16MB or more, but otherwise it runs fine. Anyway you should use a dynamic array instead of a static one if you want really large arrays. Then I decided to benchmark the code and dmd fails to compile with "Internal error: ..\ztc\cgcs.s 354". I assume the first problem has to do with memory limits and that the second is a little dmd bug. It is a bug, all internal errors are. It looks like you can avoid like this: auto tmp=(benchmark!(f0)(1000)); int time=tmp[0].to!("msecs", int);
Re: speeding up + ctfe question
On 05/27/2012 02:10 PM, maarten van damme wrote: thank you :) I wrote a sieve of aristotle because atkin's sieve needed waay to many optimizations to beat aristotle's sieve by even a little bit so I wanted to see if aristotle's was good enough. I ran in two problems. It was extremely fast when sieving a byte array of 1 million entries (without optimizations at all) but when trying with 10_000_000 entries the program crashes before it even starts to execute (main isn't reached). Then I decided to benchmark the code and dmd fails to compile with "Internal error: ..\ztc\cgcs.s 354". I assume the first problem has to do with memory limits and that the second is a little dmd bug. code is at http://dl.dropbox.com/u/15024434/d/aristotleSieve.d Yeah I get the same errors. And I'm not acquainted with the benchmark code. -- http://dlang.org/concepts.html isprime there says that 2 is not a prime. enum result = isprime(2); compile time enum "result" says false. -- http://erdani.com/d/web/phobos-prerelease/std_benchmark.html (the future) -- Er is zon buiten. Zonnige zondag namiddag met priemgetallen in de plaats van buiten zitten. Tss tss. :-)
Re: speeding up + ctfe question
thank you :) I wrote a sieve of aristotle because atkin's sieve needed waay to many optimizations to beat aristotle's sieve by even a little bit so I wanted to see if aristotle's was good enough. I ran in two problems. It was extremely fast when sieving a byte array of 1 million entries (without optimizations at all) but when trying with 10_000_000 entries the program crashes before it even starts to execute (main isn't reached). Then I decided to benchmark the code and dmd fails to compile with "Internal error: ..\ztc\cgcs.s 354". I assume the first problem has to do with memory limits and that the second is a little dmd bug. code is at http://dl.dropbox.com/u/15024434/d/aristotleSieve.d
Re: speeding up + ctfe question
On 05/27/2012 01:18 PM, maarten van damme wrote: well, maybe, looking back at it, a range isn't the ideal way to go about generating primes easily. I'm going to implement the sieve of Atkin and make it return an array of primes up to a given number. This might be a bit more useful and fast. Is there somewhere I can catch up on ctfe? after reading andrei's book and the documentation it's still not clear to me how I could make my setquicktestsize function run at compile time. https://github.com/PhilippeSigaud/D-templates-tutorial
Re: speeding up + ctfe question
well, maybe, looking back at it, a range isn't the ideal way to go about generating primes easily. I'm going to implement the sieve of Atkin and make it return an array of primes up to a given number. This might be a bit more useful and fast. Is there somewhere I can catch up on ctfe? after reading andrei's book and the documentation it's still not clear to me how I could make my setquicktestsize function run at compile time.
Re: speeding up + ctfe question
On Saturday, 26 May 2012 at 18:40:53 UTC, maarten van damme wrote: well, I was thinking about using a sieve but when you were to request prime 400_000 you're sieve would blow up in size. Because you only need primes up to sqrt(n) to check if n is prime, you can make a sieve based range that only uses O(sqrt(n)) memory. I've put an example at https://gist.github.com/2795954 .It could be optimized further (skipping even numbers, keeping track of the multiples of small primes...), but it is already much faster than a range that does not use a sieve. That's why I opted for something else (and I don't know if it was the right thing to do though). (Ab)using opIndex like that is indeed a bit wrong but what would be the alternative? remove slicing and introduce getPrime? Wouldn't that be the same but without the great syntactic sugar? Syntax sugar isn't great if it confuses people and causes bugs. You can use r.drop(n).front to get nth element of a range. If you need to do it often, you could just write a nth() function.
Re: speeding up + ctfe question
well, I was thinking about using a sieve but when you were to request prime 400_000 you're sieve would blow up in size. That's why I opted for something else (and I don't know if it was the right thing to do though). (Ab)using opIndex like that is indeed a bit wrong but what would be the alternative? remove slicing and introduce getPrime? Wouldn't that be the same but without the great syntactic sugar?
Re: speeding up + ctfe question
On Saturday, 26 May 2012 at 13:49:53 UTC, maarten van damme wrote: Is there an easy way to speed up or is this the ceiling? I got a 30 percent speedup by replacing this line: if(&& canFind(quicktestPrimes, possiblePrime)) with this: if(quicktestPrimes.back >= possiblePrime && canFind(quicktestPrimes, possiblePrime)) You could probably get a much better speedup by using some kind of a prime sieve. BTW you shouldn't be using opIndex like that. Calling opIndex shouldn't change observable state of the object and it should run in O(log(n)) or better. People expect an index operator to behave similarly to the index operator on arrays. If the function does something completely different, it is very confusing to make it an opIndex.
Re: speeding up + ctfe question
On 05/26/2012 03:49 PM, maarten van damme wrote: I finally made the primerange I wanted to make. I think I'm using a rather dumb algorithm. The idea is to store the prime we're at in curPrime and the amount of preceding primes in countPrime. Then opindex is able to calculate how many primes following or preceding curPrime we have to find to get the asked value. I'm not english so some names can be poorly chosen. Code is at http://dl.dropbox.com/u/15024434/d/primeRange.d The problem is that it's pretty slow. I wanted to find the first prime number with 10 digits and it literally takes forever (but manages it though). Is there an easy way to speed up or is this the ceiling? (better algorithms, stupidity's I've left,...) I also have an array of primes I use to "quicktest" to see if something is a prime. You can change it's size using setQuicktestSize at runtime. I want to make it large at compile time though. as I'm new to ctfe I have no idea as to how one can do this. See below for a rather dumb algorithm. The idea is to list a list of prime numbers. The problem is that it is pretty slow and you get a ... //src/main.d(57): Error: template instance main.isDivisable!(499,498) recursive expansion error when the number is too large. I'm not English so the names ARE poorly chosen. //writeln(primeList!(200)); //<---don't pick over 200 or it goes nuts //writeln(decompose!(49,2)); template primeList(int index) { static if (index > 1) { static if (isPrime!(index)) { enum int [] primeList = primeList!(index-1) ~ [index]; } else { enum int [] primeList = primeList!(index-1); } } else { enum int [] primeList = []; } } template isDivisable( int number, int divisor) { enum bool isDivisable = (number % divisor) == 0; } // 10 ---> [2,5] template decompose(int number, int d = 2) { static if (d < number) { static if (isDivisable!(number, d)) { enum int [] decompose = [d] ~ decompose!(number/d, d); } else { enum int [] decompose = decompose!(number, d+1); } } else { enum int [] decompose = [number]; } } template isPrimeDecompose(int number, int d = 2) { static if (d < number) { static if (isDivisable!(number, d)) { enum bool isPrimeDecompose = false; } else { enum bool isPrimeDecompose = isPrimeDecompose!(number, d+1); } } else { enum bool isPrimeDecompose = true; } } template isPrime(int number) { static if (number > 1) enum bool isPrime = isPrimeDecompose!(number, 2); else enum bool isPrime = false; }
speeding up + ctfe question
I finally made the primerange I wanted to make. I think I'm using a rather dumb algorithm. The idea is to store the prime we're at in curPrime and the amount of preceding primes in countPrime. Then opindex is able to calculate how many primes following or preceding curPrime we have to find to get the asked value. I'm not english so some names can be poorly chosen. Code is at http://dl.dropbox.com/u/15024434/d/primeRange.d The problem is that it's pretty slow. I wanted to find the first prime number with 10 digits and it literally takes forever (but manages it though). Is there an easy way to speed up or is this the ceiling? (better algorithms, stupidity's I've left,...) I also have an array of primes I use to "quicktest" to see if something is a prime. You can change it's size using setQuicktestSize at runtime. I want to make it large at compile time though. as I'm new to ctfe I have no idea as to how one can do this.