Re: A Friendly Challenge for D
On Tuesday, 16 October 2018 at 21:12:39 UTC, welkam wrote: On Tuesday, 16 October 2018 at 20:58:54 UTC, Jabari Zakiya wrote: And they could be modded to catch semantics like this and produce faster code. Its hard to prove that you will only write 1 or 0 in the array and even if you write such pass it wont fire very often. So slower compile times for no gain in common case. My guess is the difference in code execution times based on the ALU operation pipeline. and my guess is that CPU knows that its going to write the same value to memory so it ignores that write. Exactly. It does the same instruction twice, and once it's set the first time it can ignore setting it the second time. However with seg[k] = 1 , the mov instruction always moves, because it doesn't know|care what the previous value was. That's my guess. Life is too short for such things. Today compilers are good at optimizing low level stuff. Those decades of improvements add up. Amen! :-)
Re: A Friendly Challenge for D
On Tuesday, 16 October 2018 at 20:58:54 UTC, Jabari Zakiya wrote: And they could be modded to catch semantics like this and produce faster code. Its hard to prove that you will only write 1 or 0 in the array and even if you write such pass it wont fire very often. So slower compile times for no gain in common case. My guess is the difference in code execution times based on the ALU operation pipeline. and my guess is that CPU knows that its going to write the same value to memory so it ignores that write. I used to know most of these tricks back in the Pentium days, but I haven't had a need to keep up with Intel Ixx core chips machine|compiler > level instruction optimizations. Life is too short for such things. Today compilers are good at optimizing low level stuff. Those decades of improvements add up.
Re: A Friendly Challenge for D
On Tuesday, 16 October 2018 at 20:38:24 UTC, welkam wrote: On Tuesday, 16 October 2018 at 17:57:23 UTC, Jabari Zakiya wrote: This is the exact same behavior I found with the Nim compiler too. Well Nim compiler is more like translator. It translates Nim code to c or c++. Since gcc was responsible for optimizations and instruction selection it would be more correct to say that gcc behavior was same as llvm. How many other unknown gotchas are in the compilers? :-( the number of inlining shall be 3 https://www.youtube.com/watch?v=s4wnuiCwTGU Yes, it finally is the compiler doing it, and Clang does the same thing. And they could be modded to catch semantics like this and produce faster code. My guess is the difference in code execution times based on the ALU operation pipeline. seg[k] = seg[k] | 1 can be done "inplace" in the pipeline, where the lsb can to be changed in mem, whereas seg[k] = 1 may require a separate constant|value creation and memory write, and bypass the ALU. I used to know most of these tricks back in the Pentium days, but I haven't had a need to keep up with Intel Ixx core chips machine|compiler level instruction optimizations.
Re: A Friendly Challenge for D
On Tuesday, 16 October 2018 at 17:57:23 UTC, Jabari Zakiya wrote: This is the exact same behavior I found with the Nim compiler too. Well Nim compiler is more like translator. It translates Nim code to c or c++. Since gcc was responsible for optimizations and instruction selection it would be more correct to say that gcc behavior was same as llvm. How many other unknown gotchas are in the compilers? :-( the number of inlining shall be 3 https://www.youtube.com/watch?v=s4wnuiCwTGU
Re: A Friendly Challenge for D
On Tuesday, 16 October 2018 at 07:09:05 UTC, Vijay Nayar wrote: On Monday, 15 October 2018 at 22:17:57 UTC, Jabari Zakiya wrote: $ dub build --compiler=ldc2 -b=release && echo "30" | ./twinprimes Enter integer number: threads = 8 each thread segment is [1 x 65536] bytes array twinprime candidates = 175324676; resgroups = 1298702 each 135 threads has nextp[2 x 5566] array setup time = 1 ms, 864 μs, and 7 hnsecs perform twinprimes ssoz sieve sieve time = 196 ms, 566 μs, and 5 hnsecs last segment = 53518 resgroups; segment slices = 20 total twins = 9210144; last twin = 299712+/- 1 total time = 198 ms, 431 μs, and 2 hnsecs My understanding is that the difference in performance is largely due to slightly better optimization from the LLVM based ldc2 compiler, where I believe Nim is using gcc. Here's what I get on my system. $ echo 3_000_000_000 | ./twinprimes_test7yc.0180.gcc821 Enter integer number: threads = 8 each thread segment is [1 x 65536] bytes array twinprime candidates = 175324676; resgroups = 1298702 each 135 threads has nextp[2 x 5566] array setup time = 0.000 secs perform twinprimes ssoz sieve sieve time = 0.144 secs last segment = 53518 resgroups; segment slices = 20 total twins = 9210144; last twin = 299712+/-1 total time = 0.144 secs Hey Vijay I found subtle static typing errors. When N < 2^32 - 1 (4,294,967,295) the twimprime count and lastprime values are correct. When N > 2^32 - 1 both values start to be incorrect. Examples: For N = 4,000,000,000 you get correct answers $ echo 40 | ./twinprimes_ssoz Enter integer number: threads = 8 each thread segment is [1 x 65536] bytes array twinprime candidates = 233766231; resgroups = 1731602 each 135 threads has nextp[2 x 6332] array setup time = 667 μs and 5 hnsecs perform twinprimes ssoz sieve sieve time = 181 ms, 277 μs, and 6 hnsecs last segment = 27666 resgroups; segment slices = 27 total twins = 11944438; last twin = 399798+/- 1 total time = 181 ms, 945 μs, and 1 hnsec Examples: For N = 5,000,000,000 you get wrong answers $ echo 50 | ./twinprimes_ssoz Enter integer number: threads = 8 each thread segment is [1 x 65536] bytes array twinprime candidates = 292207792; resgroups = 2164503 each 135 threads has nextp[2 x 6999] array setup time = 744 μs and 7 hnsecs perform twinprimes ssoz sieve sieve time = 225 ms, 323 μs, and 4 hnsecs last segment = 1815 resgroups; segment slices = 34 total twins = 14618173; last twin = 705034592+/- 1 total time = 226 ms, 68 μs, and 1 hnse These are correct answers for N = 5,000,000,000 $ echo 50 | ./twinprimes_test7yc.0180.gcc821 Enter integer number: threads = 8 each thread segment is [1 x 65536] bytes array twinprime candidates = 292207792; resgroups = 2164503 each 135 threads has nextp[2 x 6999] array setup time = 0.001 secs perform twinprimes ssoz sieve sieve time = 0.237 secs last segment = 1815 resgroups; segment slices = 34 total twins = 14618166; last twin = 499860+/-1 total time = 0.237 secs The first easy check should show the lastprime value just a little smaller than N. See the timing|results table I posted earlier to see correct outputs as N gets bigger. It took me a looong time, and was a big PITA, to get the correct static typing too in Nim, especially coming from a dynamic language like Ruby.
Re: A Friendly Challenge for D
On Tuesday, 16 October 2018 at 16:57:12 UTC, welkam wrote: So I run profiler and 97% of time is spent in void twinsSieve function and hotspots are seg[k] = seg[k] | 1; lines. Since seg[k] can only be 1 or 0 I removed that or operation. And the results are. Queue the drum-roll... 5% slower. I thought that all of my studying was getting somewhere. That I beginning to understand things but no. Performing OR operation and then storing data is faster than just storing data. [sarcasm] Of course it makes sense [/sarcasm] I looked at assembler and nothing changed except orb$0x1,(%rbx,%rdi,1) is changed to movb $0x1,(%rbx,%rdi,1) I`m completely lost. This is the exact same behavior I found with the Nim compiler too. seg[k] = 1 is slower than seg[k] = seg[k] or 1, which is why it's coded like that. Thanks for finding the exact instruction difference. How many other unknown gotchas are in the compilers? :-(
Re: A Friendly Challenge for D
On Tuesday, 16 October 2018 at 07:09:05 UTC, Vijay Nayar wrote: D has multiple compilers, but for the speed of the finished binary, LDC2 is generally recommended. I used version 1.11.0. https://github.com/ldc-developers/ldc/releases/tag/v1.11.0 I was using DUB to manage the project, but to build the stand-alone file from the gist link, use this command: $ ldc2 -release -O3 twinprimes_ssoz.d And to run it: $ echo "30" | ./twinprimes_ssoz It'd be interesting to see if LTO or PGO generated an improvement. It looks like it could in this case, as it might optimize some of the inner loops. LTO is easy, enable it with: -flto= -defaultlib=phobos2-ldc-lto,druntime-ldc-lto (see: https://github.com/ldc-developers/ldc/releases/tag/v1.9.0). I've been using 'thin' on OSX, 'full' on Linux. PGO is a bit more work, but not too bad. A good primer is here: https://johanengelen.github.io/ldc/2016/07/15/Profile-Guided-Optimization-with-LDC.html --Jon
Re: A Friendly Challenge for D
So I run profiler and 97% of time is spent in void twinsSieve function and hotspots are seg[k] = seg[k] | 1; lines. Since seg[k] can only be 1 or 0 I removed that or operation. And the results are. Queue the drum-roll... 5% slower. I thought that all of my studying was getting somewhere. That I beginning to understand things but no. Performing OR operation and then storing data is faster than just storing data. [sarcasm] Of course it makes sense [/sarcasm] I looked at assembler and nothing changed except orb$0x1,(%rbx,%rdi,1) is changed to movb $0x1,(%rbx,%rdi,1) I`m completely lost.
Re: A Friendly Challenge for D
On Monday, 15 October 2018 at 22:17:57 UTC, Jabari Zakiya wrote: $ dub build --compiler=ldc2 -b=release && echo "30" | ./twinprimes Enter integer number: threads = 8 each thread segment is [1 x 65536] bytes array twinprime candidates = 175324676; resgroups = 1298702 each 135 threads has nextp[2 x 5566] array setup time = 1 ms, 864 μs, and 7 hnsecs perform twinprimes ssoz sieve sieve time = 196 ms, 566 μs, and 5 hnsecs last segment = 53518 resgroups; segment slices = 20 total twins = 9210144; last twin = 299712+/- 1 total time = 198 ms, 431 μs, and 2 hnsecs My understanding is that the difference in performance is largely due to slightly better optimization from the LLVM based ldc2 compiler, where I believe Nim is using gcc. Here's what I get on my system. $ echo 3_000_000_000 | ./twinprimes_test7yc.0180.gcc821 Enter integer number: threads = 8 each thread segment is [1 x 65536] bytes array twinprime candidates = 175324676; resgroups = 1298702 each 135 threads has nextp[2 x 5566] array setup time = 0.000 secs perform twinprimes ssoz sieve sieve time = 0.144 secs last segment = 53518 resgroups; segment slices = 20 total twins = 9210144; last twin = 299712+/-1 total time = 0.144 secs Could you list your hardware, D ver, compiler specs. I will run your code on my system with your D version and compiler, if I can. Excellent work! D has multiple compilers, but for the speed of the finished binary, LDC2 is generally recommended. I used version 1.11.0. https://github.com/ldc-developers/ldc/releases/tag/v1.11.0 I was using DUB to manage the project, but to build the stand-alone file from the gist link, use this command: $ ldc2 -release -O3 twinprimes_ssoz.d And to run it: $ echo "30" | ./twinprimes_ssoz Running the program a bunch of times, I get variable results, mostly between 195ms and 250ms. Running the Nim version, I also get variable results, mostly between 230ms and 280ms. My system is an Alienware 14x R2 from 2012. Specs can be found here: https://www.cnet.com/products/alienware-m14xr2-14-core-i7-3630qm-8-gb-ram-750-gb-hdd/specs/
Re: A Friendly Challenge for D
$ dub build --compiler=ldc2 -b=release && echo "30" | ./twinprimes Enter integer number: threads = 8 each thread segment is [1 x 65536] bytes array twinprime candidates = 175324676; resgroups = 1298702 each 135 threads has nextp[2 x 5566] array setup time = 1 ms, 864 μs, and 7 hnsecs perform twinprimes ssoz sieve sieve time = 196 ms, 566 μs, and 5 hnsecs last segment = 53518 resgroups; segment slices = 20 total twins = 9210144; last twin = 299712+/- 1 total time = 198 ms, 431 μs, and 2 hnsecs My understanding is that the difference in performance is largely due to slightly better optimization from the LLVM based ldc2 compiler, where I believe Nim is using gcc. Here's what I get on my system. $ echo 3_000_000_000 | ./twinprimes_test7yc.0180.gcc821 Enter integer number: threads = 8 each thread segment is [1 x 65536] bytes array twinprime candidates = 175324676; resgroups = 1298702 each 135 threads has nextp[2 x 5566] array setup time = 0.000 secs perform twinprimes ssoz sieve sieve time = 0.144 secs last segment = 53518 resgroups; segment slices = 20 total twins = 9210144; last twin = 299712+/-1 total time = 0.144 secs Could you list your hardware, D ver, compiler specs. I will run your code on my system with your D version and compiler, if I can. Excellent work!
Re: A Friendly Challenge for D
I don't actually understand the underlying algorithm, but I at least understand the flow of the program and the structure. The algorithm utilized depends heavily on using shared memory access, which can be done in D, but I definitely wouldn't call it idiomatic. In D, message passing is preferred, but it really can't be well demonstrated on your algorithm without a deeper understanding of the algorithm itself. A complete working version can be found at: https://gist.github.com/vnayar/79e2d0a9850833b8859dd9f08997b4d7 I modified both versions of the program to utilize the pgParameters13 for more of an apples-to-apples comparison. The final results are as follows: $ nim c --cc:gcc --d:release --threads:on twinprimes_ssoz.nim && echo "30" | ./twinprimes_ssoz Enter integer number: threads = 8 each thread segment is [1 x 65536] bytes array twinprime candidates = 175324676; resgroups = 1298702 each 135 threads has nextp[2 x 5566] array setup time = 0.000 secs perform twinprimes ssoz sieve sieve time = 0.222 secs last segment = 53518 resgroups; segment slices = 20 total twins = 9210144; last twin = 299712+/-1 total time = 0.223 secs $ dub build --compiler=ldc2 -b=release && echo "30" | ./twinprimes Enter integer number: threads = 8 each thread segment is [1 x 65536] bytes array twinprime candidates = 175324676; resgroups = 1298702 each 135 threads has nextp[2 x 5566] array setup time = 1 ms, 864 μs, and 7 hnsecs perform twinprimes ssoz sieve sieve time = 196 ms, 566 μs, and 5 hnsecs last segment = 53518 resgroups; segment slices = 20 total twins = 9210144; last twin = 299712+/- 1 total time = 198 ms, 431 μs, and 2 hnsecs My understanding is that the difference in performance is largely due to slightly better optimization from the LLVM based ldc2 compiler, where I believe Nim is using gcc. Hey Great! I'll take some time and study your code. Nim currently allows using gcc or clang: --cc:gcc or --cc:clang, and compiles to C: nim c --cc:gcc... or C++: nim c++ --cc:gcc... You can compile in Nim with/out using garbage collection (GC) and choose GC. This version needs GC to recover mem created in each thread, or it will eat it up. See operation of program using htop/top to see threads|mem at work. If D has a fast bitarray structure, try it to create the data arrays "prms" in proc "sozpg" and "seg" arrays is "twin_sieves". This could allow for larger segment sizes|arrays that fit into cpu cache, reducing the number of segment slices to process. This would all have to be profiled and encapsulated in "selectPG", which adaptively selects to best PG to use. Here is a table of output data and performance times (in seconds). The results were produced on a System76 laptop with an Intel I7 6700HQ cpu, 2.6-3.5 GHz clock, with 8 threads, and 16GB of memory. I compiled the file "twinprimes_ssoz.nim" with Nim versions 0.18.0, and the just released 0.19.0, using gcc 8.2.1 with Manjaro (Linux) in Virtual Box. I then ran the executables on my host Linux system (which only has gcc-4.9.8) to use all 8 threads. The output was produced on a "quiet" system, where I turned off the laptop and rebooted, and ran tests with only a terminal and spreedsheet open (to record results). The times are the "best" times from multiple runs. I also compare times from the program "primesieve" - https://primesieve.org/ which states on its site: primesieve is a free software program and C/C++ library that generates primes using a highly optimized sieve of Eratosthenes implementation. It counts the primes below 10^10 in just 0.45 seconds on an Intel Core i7-6700 CPU (4 x 3.4 GHz). primesieve can generate primes and prime k‑tuplets up to 2^64. (An optimized C/C++ versions of twinprimes_ssoz would be nice to compare against too.) Number | Twimprimes | Last Twinprime |twinprime_ssoz.nim, gcc-8.2.1| primesieve | ||| 0.18.0 | 0.19.0| 9.7.1| --|||--|--|| 1 x 10^09 |3424506 | 199872 | 0.043 | 0.041 | 0.049 | --|||--|--|| 5 x 10^09 | 14618166 | 499860 | 0.219 | 0.226 | 0.248 | --|||--|--|| 1 x 10^10 | 27412679 | 999702 | 0.398 | 0.401 | 0.533 | --|||--|--|| 5 x 10^10 | 118903682 |4999590 | 2.364 | 2.331 | 2.978 | --|||--|--|| 1 x 10^11 | 224376048 |762 | 4.5
Re: A Friendly Challenge for D
On Sunday, 14 October 2018 at 10:51:11 UTC, Vijay Nayar wrote: Once I get the bugs out, I'm curious to see if any performance differences crop up. There's the theory that says they should be the same, and then there's the practice. I don't actually understand the underlying algorithm, but I at least understand the flow of the program and the structure. The algorithm utilized depends heavily on using shared memory access, which can be done in D, but I definitely wouldn't call it idiomatic. In D, message passing is preferred, but it really can't be well demonstrated on your algorithm without a deeper understanding of the algorithm itself. A complete working version can be found at: https://gist.github.com/vnayar/79e2d0a9850833b8859dd9f08997b4d7 I modified both versions of the program to utilize the pgParameters13 for more of an apples-to-apples comparison. The final results are as follows: $ nim c --cc:gcc --d:release --threads:on twinprimes_ssoz.nim && echo "30" | ./twinprimes_ssoz Enter integer number: threads = 8 each thread segment is [1 x 65536] bytes array twinprime candidates = 175324676; resgroups = 1298702 each 135 threads has nextp[2 x 5566] array setup time = 0.000 secs perform twinprimes ssoz sieve sieve time = 0.222 secs last segment = 53518 resgroups; segment slices = 20 total twins = 9210144; last twin = 299712+/-1 total time = 0.223 secs $ dub build --compiler=ldc2 -b=release && echo "30" | ./twinprimes Enter integer number: threads = 8 each thread segment is [1 x 65536] bytes array twinprime candidates = 175324676; resgroups = 1298702 each 135 threads has nextp[2 x 5566] array setup time = 1 ms, 864 μs, and 7 hnsecs perform twinprimes ssoz sieve sieve time = 196 ms, 566 μs, and 5 hnsecs last segment = 53518 resgroups; segment slices = 20 total twins = 9210144; last twin = 299712+/- 1 total time = 198 ms, 431 μs, and 2 hnsecs My understanding is that the difference in performance is largely due to slightly better optimization from the LLVM based ldc2 compiler, where I believe Nim is using gcc.
Re: A Friendly Challenge for D
On Sunday, 14 October 2018 at 10:51:11 UTC, Vijay Nayar wrote: But as previous posters have said, the code is not really very different between Nim and D. Most of it is array manipulation and arithmetic operations, and not many of the features of either D or Nim are very different. Both turn into fast code, both have garbage collection, and both have generally similar operators and libraries for this kind of problem. The biggest differences I observed revolved not around the languages themselves, but around code style. Are you aware of DCompute? [1] I haven’t used it myself but since Jabari explicitly mentioned taking advantage of the GPU, it may be worth giving it a try. It should have an impact on performance and possibly on style as well, even though it will still be D. It would be nice if Nicholas could chime in on this thread. Bastiaan. [1] https://dlang.org/blog/2017/10/30/d-compute-running-d-on-the-gpu/
Re: A Friendly Challenge for D
On Saturday, 13 October 2018 at 19:04:48 UTC, Jabari Zakiya wrote: On Saturday, 13 October 2018 at 18:31:57 UTC, Vijay Nayar wrote: On Saturday, 13 October 2018 at 18:14:20 UTC, Vijay Nayar wrote: On Saturday, 13 October 2018 at 18:05:45 UTC, Jabari Zakiya wrote: It may be also running into a hard time limit imposed on compilation that Nim had/has that prevented my code from initially compiling. I'm generating a lot of PG parameter constants at compile time, and it's doing a lot of number crunching and building larger and larger arrays of constants as the PG's get larger. Try compiling with successive PG's (just P5, then P5 and P7, etc) to see where it fails. That will let you know the code is working correctly, and that the compiler is choking either/and because of a hard time limit and/or memory limit. That's why I put in a compiler output statement in 'genPGparameters' to see the progression of the PG parameters being built by the compiler to initially find when the compiler started choking. You may also need to patch whatever facility in the D compiler chain that controls this too. It's P17, the biggest one that takes the longest to build in the Nim version. I actually don't know what memory limits exist for the D compiler at compile-time, so I may need to do some homework. It's not just DMD either. $ ldc2 twinprimes_ssoz.d ... generating parameters for P17 Killed $ gdc twinprimes_ssoz.d ... generating parameters for P17 gdc: internal compiler error: Killed (program cc1d) Please submit a full bug report, with preprocessed source if appropriate. See for instructions. $ dmd twinprimes_ssoz.d ... generating parameters for P17 Killed In the Nim code, starting line 91 is when the PG constants are being generate at compile time. - # Generate at compile time the parameters for PGs P5-P17. const parametersp5 = genPGparameters(5) const parametersp7 = genPGparameters(7) const parametersp11 = genPGparameters(11) const parametersp13 = genPGparameters(13) const parametersp17 = genPGparameters(17) - Can it compile just using P5 (the first line, others commented out), and then P7, etc? I'm not understanding your comments now. If you can get a working version up and running (with correct output) we can solve the P17 compiler issues later (or in a parallel forum thread), especially if you have to delve into the weeds of the compiler chain. In my mind (same with Nim process) getting working code using any PG is first order priority (because you'll need getting multi-threading working too). Once you can do that, by default, you can then use any generator you want if you create the correct parameters for it. That's one of the advantages of the algorithm, it's PG agnostic (as long as your hardware will accommodate it). So don't prioritize getting P17 to compile right now (in this thread). Create the working generic structure that can work with any PG first. Updated: https://gist.github.com/vnayar/79e2d0a9850833b8859dd9f08997b4d7 I still get a few runtime errors likely from mistakes in my conversion for certain primes. I'll resolve those after I get back from the gym. But as previous posters have said, the code is not really very different between Nim and D. Most of it is array manipulation and arithmetic operations, and not many of the features of either D or Nim are very different. Both turn into fast code, both have garbage collection, and both have generally similar operators and libraries for this kind of problem. The biggest differences I observed revolved not around the languages themselves, but around code style. For example, can you put a loop and 3 additional statements on a single line in D? Yes. But it is considered to be not very readable code from a style perspective. Once I get the bugs out, I'm curious to see if any performance differences crop up. There's the theory that says they should be the same, and then there's the practice.
Re: A Friendly Challenge for D
On Saturday, 13 October 2018 at 18:31:57 UTC, Vijay Nayar wrote: On Saturday, 13 October 2018 at 18:14:20 UTC, Vijay Nayar wrote: On Saturday, 13 October 2018 at 18:05:45 UTC, Jabari Zakiya wrote: It may be also running into a hard time limit imposed on compilation that Nim had/has that prevented my code from initially compiling. I'm generating a lot of PG parameter constants at compile time, and it's doing a lot of number crunching and building larger and larger arrays of constants as the PG's get larger. Try compiling with successive PG's (just P5, then P5 and P7, etc) to see where it fails. That will let you know the code is working correctly, and that the compiler is choking either/and because of a hard time limit and/or memory limit. That's why I put in a compiler output statement in 'genPGparameters' to see the progression of the PG parameters being built by the compiler to initially find when the compiler started choking. You may also need to patch whatever facility in the D compiler chain that controls this too. It's P17, the biggest one that takes the longest to build in the Nim version. I actually don't know what memory limits exist for the D compiler at compile-time, so I may need to do some homework. It's not just DMD either. $ ldc2 twinprimes_ssoz.d ... generating parameters for P17 Killed $ gdc twinprimes_ssoz.d ... generating parameters for P17 gdc: internal compiler error: Killed (program cc1d) Please submit a full bug report, with preprocessed source if appropriate. See for instructions. $ dmd twinprimes_ssoz.d ... generating parameters for P17 Killed In the Nim code, starting line 91 is when the PG constants are being generate at compile time. - # Generate at compile time the parameters for PGs P5-P17. const parametersp5 = genPGparameters(5) const parametersp7 = genPGparameters(7) const parametersp11 = genPGparameters(11) const parametersp13 = genPGparameters(13) const parametersp17 = genPGparameters(17) - Can it compile just using P5 (the first line, others commented out), and then P7, etc? I'm not understanding your comments now. If you can get a working version up and running (with correct output) we can solve the P17 compiler issues later (or in a parallel forum thread), especially if you have to delve into the weeds of the compiler chain. In my mind (same with Nim process) getting working code using any PG is first order priority (because you'll need getting multi-threading working too). Once you can do that, by default, you can then use any generator you want if you create the correct parameters for it. That's one of the advantages of the algorithm, it's PG agnostic (as long as your hardware will accommodate it). So don't prioritize getting P17 to compile right now (in this thread). Create the working generic structure that can work with any PG first.
Re: A Friendly Challenge for D
On Saturday, 13 October 2018 at 18:14:20 UTC, Vijay Nayar wrote: On Saturday, 13 October 2018 at 18:05:45 UTC, Jabari Zakiya wrote: It may be also running into a hard time limit imposed on compilation that Nim had/has that prevented my code from initially compiling. I'm generating a lot of PG parameter constants at compile time, and it's doing a lot of number crunching and building larger and larger arrays of constants as the PG's get larger. Try compiling with successive PG's (just P5, then P5 and P7, etc) to see where it fails. That will let you know the code is working correctly, and that the compiler is choking either/and because of a hard time limit and/or memory limit. That's why I put in a compiler output statement in 'genPGparameters' to see the progression of the PG parameters being built by the compiler to initially find when the compiler started choking. You may also need to patch whatever facility in the D compiler chain that controls this too. It's P17, the biggest one that takes the longest to build in the Nim version. I actually don't know what memory limits exist for the D compiler at compile-time, so I may need to do some homework. It's not just DMD either. $ ldc2 twinprimes_ssoz.d ... generating parameters for P17 Killed $ gdc twinprimes_ssoz.d ... generating parameters for P17 gdc: internal compiler error: Killed (program cc1d) Please submit a full bug report, with preprocessed source if appropriate. See for instructions. $ dmd twinprimes_ssoz.d ... generating parameters for P17 Killed
Re: A Friendly Challenge for D
On Saturday, 13 October 2018 at 18:14:20 UTC, Vijay Nayar wrote: On Saturday, 13 October 2018 at 18:05:45 UTC, Jabari Zakiya wrote: It may be also running into a hard time limit imposed on compilation that Nim had/has that prevented my code from initially compiling. I'm generating a lot of PG parameter constants at compile time, and it's doing a lot of number crunching and building larger and larger arrays of constants as the PG's get larger. Try compiling with successive PG's (just P5, then P5 and P7, etc) to see where it fails. That will let you know the code is working correctly, and that the compiler is choking either/and because of a hard time limit and/or memory limit. That's why I put in a compiler output statement in 'genPGparameters' to see the progression of the PG parameters being built by the compiler to initially find when the compiler started choking. You may also need to patch whatever facility in the D compiler chain that controls this too. It's P17, the biggest one that takes the longest to build in the Nim version. I actually don't know what memory limits exist for the D compiler at compile-time, so I may need to do some homework. Yes, that's what I figured, because that's when the Nim compiler initially balked. The variable that was patched in the Nim configg file set a hard limit on number of operations the compiler could do. It's used as a break switch on a runaway process (infinite loop, etc). It's probably something like that in the D compiler too, just guessing offhand. I hope it isn't a memory limit. However, the program will run fine without using P17. It's currently selected as the optimum PG for inputs greater than 15 trillion (15,000,000,000,000), so the program will run fine and produce correct output using P13 instead, but just not as fast.
Re: A Friendly Challenge for D
On Saturday, 13 October 2018 at 18:05:45 UTC, Jabari Zakiya wrote: It may be also running into a hard time limit imposed on compilation that Nim had/has that prevented my code from initially compiling. I'm generating a lot of PG parameter constants at compile time, and it's doing a lot of number crunching and building larger and larger arrays of constants as the PG's get larger. Try compiling with successive PG's (just P5, then P5 and P7, etc) to see where it fails. That will let you know the code is working correctly, and that the compiler is choking either/and because of a hard time limit and/or memory limit. That's why I put in a compiler output statement in 'genPGparameters' to see the progression of the PG parameters being built by the compiler to initially find when the compiler started choking. You may also need to patch whatever facility in the D compiler chain that controls this too. It's P17, the biggest one that takes the longest to build in the Nim version. I actually don't know what memory limits exist for the D compiler at compile-time, so I may need to do some homework.
Re: A Friendly Challenge for D
On Saturday, 13 October 2018 at 17:36:33 UTC, Vijay Nayar wrote: On Saturday, 13 October 2018 at 15:50:06 UTC, Vijay Nayar wrote: On Saturday, 13 October 2018 at 15:19:07 UTC, Jabari Zakiya wrote: On Saturday, 13 October 2018 at 14:32:33 UTC, welkam wrote: On Saturday, 13 October 2018 at 09:22:16 UTC, Vijay Nayar wrote: [...] import algorithm thats all but then it spits out lib/nim/pure/algorithm.nim(144, 11) Error: interpretation requires too many iterations My mistake. I updated the file and forgot to include the 'import algorithm' directive. The file is now fixed to include it. Download the corrected version or patch your file accordingly. As stated in the file intro **YOU MUST DO THIS** to get it to compile with current Nim (they were supposed to fix this in this version 0.19.0 but didn't). To compile for nim versions <= 0.19.0 do following: 1) in file: ~/nim-0.19.0/compiler/vmdef.nim 2) set variable: MaxLoopIterations* = 1_000_000_000 (1 Billion or >) 3) then rebuild sysem: ./koch boot -d:release If you are using 'choosenim' to install Nim (highly advisable) the full path is: ~/.choosenim/toolchains/nim-0.19.0/compiler/vmdef.nim I'll post performance results from my laptop to give reference times to compare against. Ok, now it builds. I was previously following the build instructions from the Nim website and am not super clear what the "koch" tool does, but following your instructions, the program does build and run. I'll take a stab at making a D version. Interesting results so far. I have a partially converted program here: https://gist.github.com/vnayar/79e2d0a9850833b8859dd9f08997b4d7 The interesting part is that during compilation (with the command "dmd twinprimes_ssoz.d"), the compilation will abort with the message "Killed" and no further information. That's a new one for me, so I'm looking into the cause. It may be also running into a hard time limit imposed on compilation that Nim had/has that prevented my code from initially compiling. I'm generating a lot of PG parameter constants at compile time, and it's doing a lot of number crunching and building larger and larger arrays of constants as the PG's get larger. Try compiling with successive PG's (just P5, then P5 and P7, etc) to see where it fails. That will let you know the code is working correctly, and that the compiler is choking either/and because of a hard time limit and/or memory limit. That's why I put in a compiler output statement in 'genPGparameters' to see the progression of the PG parameters being built by the compiler to initially find when the compiler started choking. You may also need to patch whatever facility in the D compiler chain that controls this too.
Re: A Friendly Challenge for D
On Saturday, 13 October 2018 at 15:50:06 UTC, Vijay Nayar wrote: On Saturday, 13 October 2018 at 15:19:07 UTC, Jabari Zakiya wrote: On Saturday, 13 October 2018 at 14:32:33 UTC, welkam wrote: On Saturday, 13 October 2018 at 09:22:16 UTC, Vijay Nayar wrote: [...] import algorithm thats all but then it spits out lib/nim/pure/algorithm.nim(144, 11) Error: interpretation requires too many iterations My mistake. I updated the file and forgot to include the 'import algorithm' directive. The file is now fixed to include it. Download the corrected version or patch your file accordingly. As stated in the file intro **YOU MUST DO THIS** to get it to compile with current Nim (they were supposed to fix this in this version 0.19.0 but didn't). To compile for nim versions <= 0.19.0 do following: 1) in file: ~/nim-0.19.0/compiler/vmdef.nim 2) set variable: MaxLoopIterations* = 1_000_000_000 (1 Billion or >) 3) then rebuild sysem: ./koch boot -d:release If you are using 'choosenim' to install Nim (highly advisable) the full path is: ~/.choosenim/toolchains/nim-0.19.0/compiler/vmdef.nim I'll post performance results from my laptop to give reference times to compare against. Ok, now it builds. I was previously following the build instructions from the Nim website and am not super clear what the "koch" tool does, but following your instructions, the program does build and run. I'll take a stab at making a D version. Interesting results so far. I have a partially converted program here: https://gist.github.com/vnayar/79e2d0a9850833b8859dd9f08997b4d7 The interesting part is that during compilation (with the command "dmd twinprimes_ssoz.d"), the compilation will abort with the message "Killed" and no further information. That's a new one for me, so I'm looking into the cause.
Re: A Friendly Challenge for D
On Saturday, 13 October 2018 at 15:19:07 UTC, Jabari Zakiya wrote: On Saturday, 13 October 2018 at 14:32:33 UTC, welkam wrote: On Saturday, 13 October 2018 at 09:22:16 UTC, Vijay Nayar wrote: [...] import algorithm thats all but then it spits out lib/nim/pure/algorithm.nim(144, 11) Error: interpretation requires too many iterations My mistake. I updated the file and forgot to include the 'import algorithm' directive. The file is now fixed to include it. Download the corrected version or patch your file accordingly. As stated in the file intro **YOU MUST DO THIS** to get it to compile with current Nim (they were supposed to fix this in this version 0.19.0 but didn't). To compile for nim versions <= 0.19.0 do following: 1) in file: ~/nim-0.19.0/compiler/vmdef.nim 2) set variable: MaxLoopIterations* = 1_000_000_000 (1 Billion or >) 3) then rebuild sysem: ./koch boot -d:release If you are using 'choosenim' to install Nim (highly advisable) the full path is: ~/.choosenim/toolchains/nim-0.19.0/compiler/vmdef.nim I'll post performance results from my laptop to give reference times to compare against. Ok, now it builds. I was previously following the build instructions from the Nim website and am not super clear what the "koch" tool does, but following your instructions, the program does build and run. I'll take a stab at making a D version.
Re: A Friendly Challenge for D
On Saturday, 13 October 2018 at 14:32:33 UTC, welkam wrote: On Saturday, 13 October 2018 at 09:22:16 UTC, Vijay Nayar wrote: I downloaded the reference NIM implementation and got the latest nim compiler, but I received the following error: $ nim c --cc:gcc --d:release --threads:on twinprimes_ssoz.nim twinprimes_ssoz.nim(74, 11) Error: attempting to call undeclared routine: 'sort' For a person not familiar with nim, what's the fastest way to fix that? import algorithm thats all but then it spits out lib/nim/pure/algorithm.nim(144, 11) Error: interpretation requires too many iterations My mistake. I updated the file and forgot to include the 'import algorithm' directive. The file is now fixed to include it. Download the corrected version or patch your file accordingly. As stated in the file intro **YOU MUST DO THIS** to get it to compile with current Nim (they were supposed to fix this in this version 0.19.0 but didn't). To compile for nim versions <= 0.19.0 do following: 1) in file: ~/nim-0.19.0/compiler/vmdef.nim 2) set variable: MaxLoopIterations* = 1_000_000_000 (1 Billion or >) 3) then rebuild sysem: ./koch boot -d:release If you are using 'choosenim' to install Nim (highly advisable) the full path is: ~/.choosenim/toolchains/nim-0.19.0/compiler/vmdef.nim I'll post performance results from my laptop to give reference times to compare against.
Re: A Friendly Challenge for D
On Saturday, 13 October 2018 at 14:32:33 UTC, welkam wrote: On Saturday, 13 October 2018 at 09:22:16 UTC, Vijay Nayar wrote: I downloaded the reference NIM implementation and got the latest nim compiler, but I received the following error: $ nim c --cc:gcc --d:release --threads:on twinprimes_ssoz.nim twinprimes_ssoz.nim(74, 11) Error: attempting to call undeclared routine: 'sort' For a person not familiar with nim, what's the fastest way to fix that? import algorithm thats all but then it spits out lib/nim/pure/algorithm.nim(144, 11) Error: interpretation requires too many iterations I ran into the same problem as you did, and then followed the instructions from the error. I modified the compiler source and increased the number of maximum iterations from 3_000_000 to 1_000_000_000, rebuilt and installed it, but still ran into the exact same problem. There may be something up with the algorithm itself.
Re: A Friendly Challenge for D
On Saturday, 13 October 2018 at 09:22:16 UTC, Vijay Nayar wrote: I downloaded the reference NIM implementation and got the latest nim compiler, but I received the following error: $ nim c --cc:gcc --d:release --threads:on twinprimes_ssoz.nim twinprimes_ssoz.nim(74, 11) Error: attempting to call undeclared routine: 'sort' For a person not familiar with nim, what's the fastest way to fix that? import algorithm thats all but then it spits out lib/nim/pure/algorithm.nim(144, 11) Error: interpretation requires too many iterations
Re: A Friendly Challenge for D
On Friday, 12 October 2018 at 21:08:03 UTC, Jabari Zakiya wrote: On Friday, 12 October 2018 at 20:05:29 UTC, welkam wrote: On Friday, 12 October 2018 at 16:19:59 UTC, Jabari Zakiya wrote: The real point of the challenge is too see what idiomatic code... There is no idiomatic D code. There is only better implementations. D doesnt tell you how to write your code. It gives you many tools and you choose which tools to use. That`s what people like about D. I await your implementation(s)! :-) I downloaded the reference NIM implementation and got the latest nim compiler, but I received the following error: $ nim c --cc:gcc --d:release --threads:on twinprimes_ssoz.nim twinprimes_ssoz.nim(74, 11) Error: attempting to call undeclared routine: 'sort' For a person not familiar with nim, what's the fastest way to fix that?
Re: A Friendly Challenge for D
On Friday, 12 October 2018 at 20:05:29 UTC, welkam wrote: On Friday, 12 October 2018 at 16:19:59 UTC, Jabari Zakiya wrote: The real point of the challenge is too see what idiomatic code... There is no idiomatic D code. There is only better implementations. D doesnt tell you how to write your code. It gives you many tools and you choose which tools to use. That`s what people like about D. I await your implementation(s)! :-)
Re: A Friendly Challenge for D
On Friday, 12 October 2018 at 16:19:59 UTC, Jabari Zakiya wrote: The real point of the challenge is too see what idiomatic code... There is no idiomatic D code. There is only better implementations. D doesnt tell you how to write your code. It gives you many tools and you choose which tools to use. That`s what people like about D.
Re: A Friendly Challenge for D
On Friday, 12 October 2018 at 16:19:59 UTC, Jabari Zakiya wrote: Hmm,I don't think what you're saying about similar output|performance with other languages is empirically correct, but it's really not the point of the challenge. Thats why godbolt exists. c++ and Rust https://godbolt.org/z/FffXY2 C and D https://godbolt.org/z/YQvkXU Look at assembly output. Its all the same. Compilers are very good at recognizing simple arithmetic computations and can reason about it. What they struggle with is memory access. On Friday, 12 October 2018 at 16:19:59 UTC, Jabari Zakiya wrote: Finally, a really fast D implementation can be a marketing bananza to show people > in the numerical analysis, data|signal processing fields, et al, that D can be used by them to solve their problems and be more performant than C++, etc eBay`s tsv-utils is fastest in the world https://github.com/eBay/tsv-utils/blob/master/docs/comparative-benchmarks-2018.md#top-four-in-each-benchmark D`s JSON parsing is fastest in the world https://github.com/kostya/benchmarks#json Sambamba is BAM data processor and is fastest in the world https://www.basepairtech.com/blog/sorting-bam-files-samtools-vs-sambamba/ Mir GLAS is faster than OpenBLAS and Eigen http://blog.mir.dlang.io/glas/benchmark/openblas/2016/09/23/glas-gemm-benchmark.html There are enough examples but they are not enough to change minds
Re: A Friendly Challenge for D
On Friday, 12 October 2018 at 15:11:17 UTC, welkam wrote: On Wednesday, 10 October 2018 at 16:15:56 UTC, Jabari Zakiya wrote: What I am requesting here is for a person(s) who is an "expert" (very good) to create a very fast D version, using whatever tricks it has to maximize performance. I would like to include in my paper a good comparison of various implementations in different compiled languages (C/C++, D, Nim, etc) to show how it performs with each. I looked into your NIM code and from programmers point of view there is nothing interesting going on. Simple data structures and simple operations. If you wrote equivalent code in C, C++, D, NIM, Rust, Zig and compiled with same optimizing compiler (llvm or gcc) you should get the same machine code and almost the same performance (less than 1% difference due to runtime). If you got different machine code for equivalent implementation then you should file a bug report. The only way you will get different performance is by changing implementation details but then you would compare apples to oranges. Hmm,I don't think what you're saying about similar output|performance with other languages is empirically correct, but it's really not the point of the challenge. The real point of the challenge is too see what idiomatic code, written for performance, using the best resources that the language provides, will produce compared, to the Nim version. It's not to see what a line-by-line translation from Nim to D would look like. That may be a start to get something working, but shouldn't be the end goal. I'm using the Nim version here as the "reference implementation" so it can be used as the standard for comparison (accuracy of results and performance). The goal for D (et al) users is to use whatever resources it provides to maybe do better. Example. Nim currently doesn't provide standard bitarrays. Using bitarrays in place of byte arrays should perform faster because more data can fit in cache and operate faster. Also, to parallelize the algorithm maybe using OpenMP, CUDA, etc is the way to do it for D. I don't know what constructs D uses for parallel multiprocessing. And as noted before, this algorithms screams out to be done with GPUs. But you are correct that the Nim code uses very simple coding operations. That is one of its beauties! :) It is simple to understand and implement mathematically, short and simple to code, and architecturally adaptable to hardware. So to really do the challenge, the Nim code needs to be compiled and run (per instructions in code) to use as the "reference implementation", to see what correct outputs look like, and their times, and then other implementations can be compared to it. I would hope, after getting an output correct implementation done (to show you really know what you're doing) then alternative implementations can be done to wring out better performance. I think this is a good challenge for anyone wanting to learn D too, because it involves something substantially more than a "toy" algorithm, but short enough to do with minimal time and effort, that involves the need to know (learn about) D in enough detail to determine the "best" (alternative) way to do it. Finally, a really fast D implementation can be a marketing bananza to show people in the numerical analysis, data|signal processing fields, et al, that D can be used by them to solve their problems and be more performant than C++, etc. Again, people should feel free to email me if the want more direct answers to questions, or help.
Re: A Friendly Challenge for D
On Wednesday, 10 October 2018 at 16:15:56 UTC, Jabari Zakiya wrote: What I am requesting here is for a person(s) who is an "expert" (very good) to create a very fast D version, using whatever tricks it has to maximize performance. I would like to include in my paper a good comparison of various implementations in different compiled languages (C/C++, D, Nim, etc) to show how it performs with each. I looked into your NIM code and from programmers point of view there is nothing interesting going on. Simple data structures and simple operations. If you wrote equivalent code in C, C++, D, NIM, Rust, Zig and compiled with same optimizing compiler (llvm or gcc) you should get the same machine code and almost the same performance (less than 1% difference due to runtime). If you got different machine code for equivalent implementation then you should file a bug report. The only way you will get different performance is by changing implementation details but then you would compare apples to oranges.
Re: A Friendly Challenge for D
On 10/11/2018 10:14 AM, Jabari Zakiya wrote: > Ok, hopefully this will work for everyone. Try this link: > > https://mega.nz/#!yJxUEQgK!MY9dwjiWheE8tACtEeS0szduIvdBjiyTn4O6mMD_aZw Thank you. That worked just fine. I clicked the Download link and the pdf was saved on my end. :) Ali
Re: A Friendly Challenge for D
On Thursday, 11 October 2018 at 16:13:17 UTC, Jabari Zakiya wrote: On Thursday, 11 October 2018 at 14:49:54 UTC, Carl Sturtivant wrote: On Thursday, 11 October 2018 at 13:26:19 UTC, Jabari Zakiyth wrote: On Thursday, 11 October 2018 at 05:11:20 UTC, Ali Çehreli wrote: [...] What country are you trying to get access from, because I know people in the US have gotten the papers from those link, for free and without an account. It may also have something to do with your browser. They work for me in various modern browsers, including the Tor Browser. Not credible --- I cannot get either without an account browsing from the US using Firefox with no unusual arrangements. Wow. Those links used to work with no problem, so I don't know what is it (vpn use, etc,?). OK, this will definitely work. Send me an email and I will email you the paper (and figure out a sure fire way to make it available). Construct this full email (for humans). (my first initial)(lastname) at gmail Ok, hopefully this will work for everyone. Try this link: https://mega.nz/#!yJxUEQgK!MY9dwjiWheE8tACtEeS0szduIvdBjiyTn4O6mMD_aZw However, I'm still interested to find out what is|are the specific issues with the other links so I can make a possible bug report to those services. 1) Can you actually get to the site? 2) Can you see the document (a reference to it)? 3) Can you read the document online (did you try)? 4) What happened when you tried to download it (popup requiring account, etc)? The paper is from 2014, Scribd has changed a lot since then. The more information people can provide will help me determine how to provide better access to them. But you can always email me to get them as a last resort, or just to ask questions.
Re: A Friendly Challenge for D
On Thursday, 11 October 2018 at 14:49:54 UTC, Carl Sturtivant wrote: On Thursday, 11 October 2018 at 13:26:19 UTC, Jabari Zakiyth wrote: On Thursday, 11 October 2018 at 05:11:20 UTC, Ali Çehreli wrote: [...] What country are you trying to get access from, because I know people in the US have gotten the papers from those link, for free and without an account. It may also have something to do with your browser. They work for me in various modern browsers, including the Tor Browser. Not credible --- I cannot get either without an account browsing from the US using Firefox with no unusual arrangements. Wow. Those links used to work with no problem, so I don't know what is it (vpn use, etc,?). OK, this will definitely work. Send me an email and I will email you the paper (and figure out a sure fire way to make it available). Construct this full email (for humans). (my first initial)(lastname) at gmail
Re: A Friendly Challenge for D
On Thursday, 11 October 2018 at 13:26:19 UTC, Jabari Zakiyth wrote: On Thursday, 11 October 2018 at 05:11:20 UTC, Ali Çehreli wrote: [...] What country are you trying to get access from, because I know people in the US have gotten the papers from those link, for free and without an account. It may also have something to do with your browser. They work for me in various modern browsers, including the Tor Browser. Not credible --- I cannot get either without an account browsing from the US using Firefox with no unusual arrangements.
Re: A Friendly Challenge for D
On Thursday, 11 October 2018 at 05:11:20 UTC, Ali Çehreli wrote: On 10/10/2018 07:52 PM, Jabari Zakiyth wrote: > On Wednesday, 10 October 2018 at 22:25:17 UTC, Neia Neutuladh wrote: >> On 10/10/2018 03:05 PM, Jabari Zakiya wrote: >>> https://www.scribd.com/doc/228155369/The-Segmented-Sieve-of-Zakiya-SSoZ >> >> It would be great if you could provide a link to a freely downloadable >> version of this. > > You can download the paper for free from that link. Did you have trouble > doing it? I think the problem is, scribd requires an account, which they apparently happy to link to an existing Google or Facebook account. > Here's another link to paper. > > https://www.academia.edu/7583194/The_Segmented_Sieve_of_Zakiya_SSoZ_ Similarly, that one requires a Google account. > Here, again, is the link to the Nim code. Just install Nim (current > 0.19.0) and compile and run it per instructions in code. I recommend > people do that to see its outputs and verify its results. > > https://gist.github.com/jzakiya/6c7e1868bd749a6b1add62e3e3b2341e That works! :) Ali What country are you trying to get access from, because I know people in the US have gotten the papers from those link, for free and without an account. It may also have something to do with your browser. They work for me in various modern browsers, including the Tor Browser.
Re: A Friendly Challenge for D
On 10/10/2018 07:52 PM, Jabari Zakiyth wrote: > On Wednesday, 10 October 2018 at 22:25:17 UTC, Neia Neutuladh wrote: >> On 10/10/2018 03:05 PM, Jabari Zakiya wrote: >>> https://www.scribd.com/doc/228155369/The-Segmented-Sieve-of-Zakiya-SSoZ >> >> It would be great if you could provide a link to a freely downloadable >> version of this. > > You can download the paper for free from that link. Did you have trouble > doing it? I think the problem is, scribd requires an account, which they apparently happy to link to an existing Google or Facebook account. > Here's another link to paper. > > https://www.academia.edu/7583194/The_Segmented_Sieve_of_Zakiya_SSoZ_ Similarly, that one requires a Google account. > Here, again, is the link to the Nim code. Just install Nim (current > 0.19.0) and compile and run it per instructions in code. I recommend > people do that to see its outputs and verify its results. > > https://gist.github.com/jzakiya/6c7e1868bd749a6b1add62e3e3b2341e That works! :) Ali
Re: A Friendly Challenge for D
On Thursday, 11 October 2018 at 00:22:10 UTC, tide wrote: On Wednesday, 10 October 2018 at 16:15:56 UTC, Jabari Zakiya wrote: I would like to include in my paper a good comparison of various implementations in different compiled languages (C/C++, D, Nim, etc) to show how it performs with each. If you want help with your paper, possibly some kind of decent financial incentive would be appropriate. If the algorithm benefits from more threads than finding or creating an implementation that runs on a GPU would probably be the true performance test. CPUs have like 4-8 cores in the mainstream? A GPU has hundreds, though with some limitations. I'm writing the paper anyway (just like the others), so other implementations are icing on the cake to show implementation variations, as a benefit to readers. Maybe if I set up a website and created a Rosetta Code repo for people to post their different language implementations, and offer a T-shirt for fastest implementation. :-) Yes, a GPU based implementation would be the epitome for this algorithm, by far. This is actually why I have gotten the algorithm to this implementation so that the number crunching can all be done in parallel threads. (It would also be screamingly fast done in hardware in a FPGA too.) However, I only have standard consumer grade laptops. Hopefully someone(s) with sufficient hardware, interest, and time, will take this upon themselves to do this and publicize their results.
Re: A Friendly Challenge for D
On Wednesday, 10 October 2018 at 22:25:17 UTC, Neia Neutuladh wrote: On 10/10/2018 03:05 PM, Jabari Zakiya wrote: https://www.scribd.com/doc/228155369/The-Segmented-Sieve-of-Zakiya-SSoZ It would be great if you could provide a link to a freely downloadable version of this. You can download the paper for free from that link. Did you have trouble doing it? Here's another link to paper. https://www.academia.edu/7583194/The_Segmented_Sieve_of_Zakiya_SSoZ_ Here, again, is the link to the Nim code. Just install Nim (current 0.19.0) and compile and run it per instructions in code. I recommend people do that to see its outputs and verify its results. https://gist.github.com/jzakiya/6c7e1868bd749a6b1add62e3e3b2341e
Re: A Friendly Challenge for D
On Wednesday, 10 October 2018 at 16:15:56 UTC, Jabari Zakiya wrote: I would like to include in my paper a good comparison of various implementations in different compiled languages (C/C++, D, Nim, etc) to show how it performs with each. If you want help with your paper, possibly some kind of decent financial incentive would be appropriate. If the algorithm benefits from more threads than finding or creating an implementation that runs on a GPU would probably be the true performance test. CPUs have like 4-8 cores in the mainstream? A GPU has hundreds, though with some limitations.
Re: A Friendly Challenge for D
On 10/10/2018 03:05 PM, Jabari Zakiya wrote: https://www.scribd.com/doc/228155369/The-Segmented-Sieve-of-Zakiya-SSoZ It would be great if you could provide a link to a freely downloadable version of this.
Re: A Friendly Challenge for D
On Wednesday, 10 October 2018 at 20:43:01 UTC, Kagamin wrote: On Wednesday, 10 October 2018 at 16:15:56 UTC, Jabari Zakiya wrote: https://gist.github.com/jzakiya/6c7e1868bd749a6b1add62e3e3b2341e As i understand, main thread preallocates global memory and tracks it, and other threads don't track it? Here's an abreviated elementary explanation of the algorithm and implementation. You will need to read (download) my paper "The Segmented Sieve of Zakiya (SSoZ)" because I will make reference to things in it, to keep this as short as possible. https://www.scribd.com/doc/228155369/The-Segmented-Sieve-of-Zakiya-SSoZ To really understand the math and theory of the algorithm requires primarily just understanding Table 3 on page 3 of the paper, as it encapsulates everything. You can read the paper to understand the language of the algorithm used in the code. Twinprimes are 2 (odd) primes that differ by only 2 eg. 3-5, 5-7, 11-13, 29-31. Table 3 shows all the residues values (prime candidates|pcs) and residues groups (resgroups|columns) to find all the primes upto 541 using P5 (modpg = 30, rescnt = 8). For a given value N, it will be represented with a PG table of some number of resgroups, with max size I call Kmax (the regroups value N residues in). Using P5, I only need to sieve primes along the residue tracks (restracks) that can produce twinprimes, here 11-13, 17-19, 29-31. Thus I create 3 byte arrays, one for each twinpair, and use the lower 2 bits to represent the upper and lower twinprime restracks. Then for each twinpair (here 3) I run 3 thread which perform the SSoZ on the entire Kmax length of resgroups in parallel. At the end I accumulate the results and print them out. This, in a nutshell, is what the algorithm does. The paper gives you enough to understand the fundamental nature of the algorithm, though I've learned so much more than in 2014. :) The larger the PG the more twinpair restracks (see page 14) there are to use. For larger numbers you want to use the largest PG possible that 'fits' into the hardware cpu. All my development|testing was done on laptops using Intel I5|I7 cpus with 4 or 8 threads. I'm really interested how it performs on other platforms (ARM, AMD, PowerPC, etc). The main proc "twinprimes_ssoz" manages program flow and set as follows: 1) accepts the input number (an integer) in "val" from the cli 2) sets "num" to be first odd number < "val" if "val" even 3) calls "selectPG" with "num" to select optimum Prime Generator (PG) parameters 4) compute various working parameters per selected PG and number value (see refs) 5) compute global values for number of primes, and their values, <= sqrt(num) for selected PG with proc "sozpg" 6) Set initial twinprime count for selected PG 7) Then with proc "segsieve" allocate one thread to perform SSoZ (segmented sieve of zakiya) on each twinprime pair residues (determined by selected PG), and count number of twinprmes computed in each thread. 8) Then determine true total twinprime count and last twinprime <= "num" It also is timing different intervals and prints out diagnostics and final output. The proc "twins_sieve" is the primary function that manages and performs the SSoZ for a given twinprim pair parameters in each thread. The more threads the faster the process goes. I'll provide more info later. I have to run now. I wanted to get this out now while I was at my laptop, and online.
Re: A Friendly Challenge for D
On Wednesday, 10 October 2018 at 16:15:56 UTC, Jabari Zakiya wrote: https://gist.github.com/jzakiya/6c7e1868bd749a6b1add62e3e3b2341e As i understand, main thread preallocates global memory and tracks it, and other threads don't track it?
Re: A Friendly Challenge for D
On Wednesday, 10 October 2018 at 16:15:56 UTC, Jabari Zakiya wrote: [...] Looking forward to this :)
A Friendly Challenge for D
Hi. I hope this is the right place to request this, if not please tell me a better one. I had looked at D, and played with it some circa 2010~2012, but time and life took my priorities away. But I'm still interested in learning different languages, but there are so many more now it's hard to devote the time to learn them to some high level of proficiency. Subsequently, I started learning Nim, because I find the syntax and constructs simpler and more familiar than most (I'm coming mostly from a Ruby background). I have developed in Nim a program to find twinprimes that seems to be the fastest of its type, compared to primesieve (https://primesieve.org/) which claims to be the fastest, written in C++. Here is the code to my Nim implementation of twinprimes_ssoz. https://gist.github.com/jzakiya/6c7e1868bd749a6b1add62e3e3b2341e The total file is just 318 lines of code, with about 60 separate lines of comments. The code is extensively commented per line to explain what's happening. Reading the references given in the code introduction will explain the general process. See "The Segmented Sieve of Zakiya (SSoZ)" https://www.scribd.com/doc/228155369/The-Segmented-Sieve-of-Zakiya-SSoZ I am in the process of writing up a paper to explain this application, and implementation. What I am requesting here is for a person(s) who is an "expert" (very good) to create a very fast D version, using whatever tricks it has to maximize performance. I would like to include in my paper a good comparison of various implementations in different compiled languages (C/C++, D, Nim, etc) to show how it performs with each. This algorithm is designed to be run in multiprocessing environments (more core/threads, better performance). The Nim version (0.18.0, 0.19.0 recently released) uses its native parallel processing structure. In C++, et al, it may be best implemented using OPenMP, or CUDA, etc. These are implementation details one versed in a language could determine. Well that's it. I am willing to share performance data, compared to primesive, if you like. The beauty of this algorithm|implementation is its simplicity in design, and minimal code. It shouldn't be that hard to understand to determine how to translate into D. Of course, I'm am fully available to answer questions and provide help. Thanks Jabari
Re: Knowing the approach to solve a D challenge
On Friday, 16 February 2018 at 09:44:27 UTC, aberba wrote: D has tone of features and library solutions. When you encounter a problem, how do you approach solving it in code? 1. Do you first write it in idiomatic D style or a more general approach before porting to idiomatic D? Like always, it depends. Do I attribute up all my functions with const/@safe/nothrow... (is that even idiomatic) no. Do I build a range to process some data... sometimes. Do I utilize std.algorithm/std.range functions to process my data... when available. Even my C# code tends to be more idiomatic D than others. 2. Do you find yourself mostly rolling out your own implementation first before using a library function? I don't know. If a rolled my own I probably don't know of the library function/function combination that does the same thing. 3. Do the use of generics come out of first try or a rewrite? Usually not. If I don't have another use-case I probably don't know what needs to be generic. 4. What rough percentage of phobos knowledge is required for reasonable good problem solving efficiency? I would guess average. The reason I say this because unlike popular languages search doesn't always provide a good example for every question so you kind of need to already know what you're looking for. It doesn't help that sometimes the answer is a combination of this (.reduce!max that isn't found in std.math)
Re: Knowing the approach to solve a D challenge
On Friday, 16 February 2018 at 09:44:27 UTC, aberba wrote: 1. Do you first write it in idiomatic D style or a more general approach before porting to idiomatic D? In micro-level, it's usually fairly idiomatic from get-go. Usually no heap allocations at inner loops, for-looping, static variables etc. Sometimes if I get a bit desperate of frustated I might do this a bit. But at larger level, I often find myself shifting work between functions, structs, modules and so. In other words, redesigning. 2. Do you find yourself mostly rolling out your own implementation first before using a library function? No, the vast majority of my calls are from Phobos or other libraries I use. And in case of Phobos at least, it's stuff is so general that I don't need to design my own function often. An exception is std.algorithm.each, but just to get better error messages (template constraints don't tell why the call did not work). 3. Do the use of generics come out of first try or a rewrite? Rewriting a lot, but that's the case with all coding. With generics, i often tend to forget ! before an alias parameter. 4. What rough percentage of phobos knowledge is required for reasonable good problem solving efficiency? If we talk about experience of the language in general, it's more than with C-style programming, Java or C# but less than with C++ generics. I don't think you have to know Phobos throughout, but you have to know the language and understand the philosophy of ranges quite deeply. Percentages aren't important, I think that as long as you know the general purpose of std.algorithm, std.range, std.stdio, std.conv and std.array that gets you started. Again, if you know the language and understand the range concept.
Re: Knowing the approach to solve a D challenge
On Friday, 16 February 2018 at 09:44:27 UTC, aberba wrote: D has tone of features and library solutions. When you encounter a problem, how do you approach solving it in code? 1. Do you first write it in idiomatic D style or a more general approach before porting to idiomatic D? As idiomatic as possible. But it depends on how big and/or important the method/function is. The more important and/or bigger, the more idiomatic. Sometimes a `foreach` will do in a small function. But D makes it easy to write idiomatic code straight away, although sometimes it can be a bit annoying when you get messages like "cannot implicitly convert x of type y to z". So you have to keep track of what you are chaining. 2. Do you find yourself mostly rolling out your own implementation first before using a library function? I usually start to roll out my own for a few minutes until I say "Hold on, maybe the library already has a function that does exactly that!" And it often does. That's because I get a better understanding of what I need, when I roll my own for a while. Using the library straight away can sometimes result in shooting yourself in the foot. So it's a mix of both. 3. Do the use of generics come out of first try or a rewrite? Depends on the problem at hand. I you know you will have to handle several types down the road, it's a minimal generic that accepts only one type to begin with but that can be extended to others. It's a bit "play by ear". If I'm dealing with HTML and I know that JSON or CSV will be needed later, I write the function in a way that it can easily be extended. If a function returns the user name as a `string`, I won't bother with generics. That's just normal, I think. 4. What rough percentage of phobos knowledge is required for reasonable good problem solving efficiency? You cannot know every function, of course, and new functions are being added all the time. What you need to know is what Phobos can do in general and where to look for it. The cheat sheet should be the first port of call. You can save a lot of time by skimming through the library regularly. Also, it's worth looking at other people's code in the "learn" section. What often happens to me, when I see a solution, I go "Jesus, that's clever, I'll keep that in mind!" The learn section is good because it focuses on one (small) problem at a time.
Re: Knowing the approach to solve a D challenge
I don't write much D code, but here are my answers for _any_ language. On Friday, 16 February 2018 at 09:44:27 UTC, aberba wrote: D has tone of features and library solutions. When you encounter a problem, how do you approach solving it in code? 1. Do you first write it in idiomatic D style or a more general approach before porting to idiomatic D? The style in my head, which sometimes is D function chains, for example, this chain I put in Phobos: https://github.com/dlang/phobos/blob/master/std/datetime/timezone.d#L2501 Compare it to the previously-written non-Android version just below, which could probably be written as such a chain but might be too unwieldy if done that way. 2. Do you find yourself mostly rolling out your own implementation first before using a library function? Look for a library function, and if nothing works, write your own. 3. Do the use of generics come out of first try or a rewrite? I don't really need them for my own functions, so can't say. 4. What rough percentage of phobos knowledge is required for reasonable good problem solving efficiency? Just hunt for something when you need it. Knowing Phobos well is like indexing your data beforehand, you'll find something much quicker. The reason D supports so many styles is so you don't have to force yourself to use only one style. The D idioms are there if you need them though, and you may find using them gives you better code.
Re: Knowing the approach to solve a D challenge
On 16/02/2018 9:44 AM, aberba wrote: D has tone of features and library solutions. When you encounter a problem, how do you approach solving it in code? 1. Do you first write it in idiomatic D style or a more general approach before porting to idiomatic D? 2. Do you find yourself mostly rolling out your own implementation first before using a library function? 3. Do the use of generics come out of first try or a rewrite? 4. What rough percentage of phobos knowledge is required for reasonable good problem solving efficiency? A: Do it any way possible If it needs a rewrite then yes more idiomatic and better designed :)
Knowing the approach to solve a D challenge
D has tone of features and library solutions. When you encounter a problem, how do you approach solving it in code? 1. Do you first write it in idiomatic D style or a more general approach before porting to idiomatic D? 2. Do you find yourself mostly rolling out your own implementation first before using a library function? 3. Do the use of generics come out of first try or a rewrite? 4. What rough percentage of phobos knowledge is required for reasonable good problem solving efficiency?
Challenge on Russian Stack Overflow
I found funny (from my point of view) challenge in Russian Stack
Overflow.
Any language accepted.
You need to make the loop
for (int x=0; x<3; ++x) {}
endless.
Rules:
- you can't modify the loop's code itself;
- you can't modify the loop's variable inside the body of loop;
- you can't wrap the loop in an outer infinite loop or insert an
infinite loop inside the body;
For example, C++ solution:
int main() {
#define int bool
for (int x=0; x<3; ++x);
return 0;
}
This is my D solution -
http://ru.stackoverflow.com/a/589748/218208
Solution with the highest rating wins.
Re: Challenge
On 6 October 2016 at 01:07, Jonathan M Davis via Digitalmars-d
wrote:
> On Thursday, October 06, 2016 00:38:54 Manu via Digitalmars-d wrote:
>> I thought there was a distinction between typetuple and alias? Some
>> expression can be captured by a typetuple, but not by alias?
>> There must be a reason for that horrible and prolific pattern "(T...)
>> if(T.length == 1) { ... T[0] ... }" instead of "(alias T) { ... T ...
>> }"?
>
> That has to do with the fact alias template parameters don't take keywords,
> even if they're types. alias declarations don't have that problem. If they
> did, we couldn't have stuff like size_t or c_long. In theory, Walter has
> agreed that we'll fix it so that template alias parameters are consistent
> with alias declarations, but that hasn't happened yet. And until it does,
> we're stuck with the weird variadic templates of length 1.
I see. It sounds like one of these things that needs a serious priority boost.
There are a lot of weirdness-es in template code that make is SO HARD
for non-absolute-experts to understand. It's practically impossible to
author correct code unless you are a serious forum regular of a phobos
contributor.
These weird patterns that are effectively workarounds need to be
ejected into space as soon as possible. I get seriously embarrassed
every time I have to explain these sorts of things to one my
colleagues!
Re: Challenge
On Thursday, October 06, 2016 00:38:54 Manu via Digitalmars-d wrote:
> I thought there was a distinction between typetuple and alias? Some
> expression can be captured by a typetuple, but not by alias?
> There must be a reason for that horrible and prolific pattern "(T...)
> if(T.length == 1) { ... T[0] ... }" instead of "(alias T) { ... T ...
> }"?
That has to do with the fact alias template parameters don't take keywords,
even if they're types. alias declarations don't have that problem. If they
did, we couldn't have stuff like size_t or c_long. In theory, Walter has
agreed that we'll fix it so that template alias parameters are consistent
with alias declarations, but that hasn't happened yet. And until it does,
we're stuck with the weird variadic templates of length 1.
- Jonathan M Davis
Re: Challenge
On 5 October 2016 at 19:45, Jonathan M Davis via Digitalmars-d
wrote:
> On Wednesday, October 05, 2016 09:24:56 John Colvin via Digitalmars-d wrote:
>> > It _is_ however recommended to use __traits(getMember, T,
>> > member) over manually building it with strings with something
>> > like T.stringof ~ "." ~ member, because the string manipulation
>> > falls about in corner cases (e.g. it could result in a symbol
>> > conflict). It's just that then has the unfortunate side effect
>> > of requiring AliasSeq because of the bug.
>> >
>> > - Jonathan M Davis
>>
>> https://dlang.org/phobos/std_meta.html#.Alias :)
>
> IMHO, that doesn't improve things much, but it is slightly shorter. Thanks
> for pointing it out.
I thought there was a distinction between typetuple and alias? Some
expression can be captured by a typetuple, but not by alias?
There must be a reason for that horrible and prolific pattern "(T...)
if(T.length == 1) { ... T[0] ... }" instead of "(alias T) { ... T ...
}"?
Re: Challenge
On Wednesday, October 05, 2016 09:24:56 John Colvin via Digitalmars-d wrote: > > It _is_ however recommended to use __traits(getMember, T, > > member) over manually building it with strings with something > > like T.stringof ~ "." ~ member, because the string manipulation > > falls about in corner cases (e.g. it could result in a symbol > > conflict). It's just that then has the unfortunate side effect > > of requiring AliasSeq because of the bug. > > > > - Jonathan M Davis > > https://dlang.org/phobos/std_meta.html#.Alias :) IMHO, that doesn't improve things much, but it is slightly shorter. Thanks for pointing it out. - Jonathan M Davis
Re: Challenge
On Wednesday, 5 October 2016 at 02:15:13 UTC, Jonathan M Davis
wrote:
On Wednesday, October 05, 2016 11:20:44 Manu via Digitalmars-d
wrote:
> While you're at it, might I suggest also adding
> std.traits.isProperty?
>
> Something like:
> template isProperty(T, string member)
> {
>
> import std.meta : AliasSeq;
> import std.traits : FunctionTypeOf;
> alias sym = AliasSeq!(__traits(getMember, T, member))[0];
> enum isProperty = !is(typeof(sym) == function) &&
>
> is(FunctionTypeOf!(typeof(&sym)) == function);
> }
Why this AliasSeq business? That line is rather an
abomination... why are all these horrible expressions popping
up as recommendations nowadays?
The AliasSeq muck is there because for some reason you can't
alias the result of __traits, so doing something like
alias sym = __traits(getMember, T, member);
isn't legal. So, this has nothing to do with a recommendation
of best practice and everything to do with an annoying bug.
https://issues.dlang.org/show_bug.cgi?id=7804
It _is_ however recommended to use __traits(getMember, T,
member) over manually building it with strings with something
like T.stringof ~ "." ~ member, because the string manipulation
falls about in corner cases (e.g. it could result in a symbol
conflict). It's just that then has the unfortunate side effect
of requiring AliasSeq because of the bug.
- Jonathan M Davis
https://dlang.org/phobos/std_meta.html#.Alias :)
Re: Challenge
On Wednesday, 5 October 2016 at 02:15:13 UTC, Jonathan M Davis wrote: The AliasSeq muck is there because for some reason you can't alias the result of __traits, so doing something like alias sym = __traits(getMember, T, member); isn't legal. So, this has nothing to do with a recommendation of best practice and everything to do with an annoying bug. When aliasing a single symbol, I find it much cleaner to use... Identity!(...) or I!(...) ... instead of AliasSeq!(...)[0]
Re: Challenge
On Wednesday, October 05, 2016 11:20:44 Manu via Digitalmars-d wrote:
> > While you're at it, might I suggest also adding std.traits.isProperty?
> >
> > Something like:
> > template isProperty(T, string member)
> > {
> >
> > import std.meta : AliasSeq;
> > import std.traits : FunctionTypeOf;
> > alias sym = AliasSeq!(__traits(getMember, T, member))[0];
> > enum isProperty = !is(typeof(sym) == function) &&
> >
> > is(FunctionTypeOf!(typeof(&sym)) == function);
> > }
>
> Why this AliasSeq business? That line is rather an abomination... why
> are all these horrible expressions popping up as recommendations
> nowadays?
The AliasSeq muck is there because for some reason you can't alias the
result of __traits, so doing something like
alias sym = __traits(getMember, T, member);
isn't legal. So, this has nothing to do with a recommendation of best
practice and everything to do with an annoying bug.
https://issues.dlang.org/show_bug.cgi?id=7804
It _is_ however recommended to use __traits(getMember, T, member) over
manually building it with strings with something like T.stringof ~ "." ~
member, because the string manipulation falls about in corner cases (e.g. it
could result in a symbol conflict). It's just that then has the unfortunate
side effect of requiring AliasSeq because of the bug.
- Jonathan M Davis
Re: Challenge
On 4 October 2016 at 22:48, Manu wrote:
> On 4 October 2016 at 14:40, Jonathan M Davis via Digitalmars-d
> wrote:
>> On Tuesday, October 04, 2016 14:24:59 Manu via Digitalmars-d wrote:
>>> On 4 October 2016 at 12:30, Jonathan M Davis via Digitalmars-d
>>>
>>> wrote:
>>> > On Tuesday, October 04, 2016 11:13:36 Manu via Digitalmars-d wrote:
>>> >> I'm feeling John's solution is a little bit simpler. But nice work,
>>> >> thanks!
>>> >
>>> > So, it is. LOL. I'd actually glanced over that post while I was in the
>>> > middle of getting my version to work, and I read it too quickly, because I
>>> > understood that it had just solved the property problem and that it didn't
>>> > work for all cases. I'll have to update my PR. Though his code does make
>>> > the mistake of doing
>>> >
>>> > mixin(`alias mem = T.` ~ member ~ `;`);
>>> >
>>> > rather than doing something like
>>> >
>>> > alias mem = AliasSeq!(__traits(getMember, T, member))[0];
>>> >
>>> > which means that there are some cases where it won't work properly. The
>>> > core logic is simpler though, which is definitely a plus.
>>>
>>> Make that change in your PR :)
>>
>> I already updated it and was actually able to make it slightly simpler than
>> John's example (as far as I can tell, FunctionTypeOf is only needed in the
>> case where the address is taken).
>>
>>> I think the PR is important. It's not obvious how to do this, and it's
>>> very useful. I was astonished it's not already there.
>>
>> Yeah. I ran into a need for something similar recently, but my
>> implementation at the time wasn't as thorough, since it just used offsetof
>> to do the check (though in my case, I think that was enough). Getting it
>> completely right is surprisingly difficult.
>>
>> I was also surprised that while we have quite a few __traits for functions,
>> they're severely lacking for variables (e.g. I was looking for the variable
>> equivalent of __traits(isStaticFunction, ...), and there is no such beast).
>> For that matter, even testing whether something is a variable is
>> surprisingly difficult.
>>
>> - Jonathan M Davis
>
> While you're at it, might I suggest also adding std.traits.isProperty?
> Something like:
>
> template isProperty(T, string member)
> {
> import std.meta : AliasSeq;
> import std.traits : FunctionTypeOf;
> alias sym = AliasSeq!(__traits(getMember, T, member))[0];
> enum isProperty = !is(typeof(sym) == function) &&
> is(FunctionTypeOf!(typeof(&sym)) == function);
> }
Why this AliasSeq business? That line is rather an abomination... why
are all these horrible expressions popping up as recommendations
nowadays?
Re: Challenge
On 4 October 2016 at 14:40, Jonathan M Davis via Digitalmars-d
wrote:
> On Tuesday, October 04, 2016 14:24:59 Manu via Digitalmars-d wrote:
>> On 4 October 2016 at 12:30, Jonathan M Davis via Digitalmars-d
>>
>> wrote:
>> > On Tuesday, October 04, 2016 11:13:36 Manu via Digitalmars-d wrote:
>> >> I'm feeling John's solution is a little bit simpler. But nice work,
>> >> thanks!
>> >
>> > So, it is. LOL. I'd actually glanced over that post while I was in the
>> > middle of getting my version to work, and I read it too quickly, because I
>> > understood that it had just solved the property problem and that it didn't
>> > work for all cases. I'll have to update my PR. Though his code does make
>> > the mistake of doing
>> >
>> > mixin(`alias mem = T.` ~ member ~ `;`);
>> >
>> > rather than doing something like
>> >
>> > alias mem = AliasSeq!(__traits(getMember, T, member))[0];
>> >
>> > which means that there are some cases where it won't work properly. The
>> > core logic is simpler though, which is definitely a plus.
>>
>> Make that change in your PR :)
>
> I already updated it and was actually able to make it slightly simpler than
> John's example (as far as I can tell, FunctionTypeOf is only needed in the
> case where the address is taken).
>
>> I think the PR is important. It's not obvious how to do this, and it's
>> very useful. I was astonished it's not already there.
>
> Yeah. I ran into a need for something similar recently, but my
> implementation at the time wasn't as thorough, since it just used offsetof
> to do the check (though in my case, I think that was enough). Getting it
> completely right is surprisingly difficult.
>
> I was also surprised that while we have quite a few __traits for functions,
> they're severely lacking for variables (e.g. I was looking for the variable
> equivalent of __traits(isStaticFunction, ...), and there is no such beast).
> For that matter, even testing whether something is a variable is
> surprisingly difficult.
>
> - Jonathan M Davis
While you're at it, might I suggest also adding std.traits.isProperty?
Something like:
template isProperty(T, string member)
{
import std.meta : AliasSeq;
import std.traits : FunctionTypeOf;
alias sym = AliasSeq!(__traits(getMember, T, member))[0];
enum isProperty = !is(typeof(sym) == function) &&
is(FunctionTypeOf!(typeof(&sym)) == function);
}
Re: Challenge
On 4 October 2016 at 14:40, Jonathan M Davis via Digitalmars-d wrote: > [...] > For that matter, even testing whether something is a variable is > surprisingly difficult. True story! I've written that one before... I spent ages trying to get it right! When people say D is highly complex, these are the reasons. There are a lot of edges, and some arbitrary corners where things just don't work. *mutter mutter* storage class *mutter mutter*
Re: Challenge
On Tuesday, October 04, 2016 14:24:59 Manu via Digitalmars-d wrote: > On 4 October 2016 at 12:30, Jonathan M Davis via Digitalmars-d > > wrote: > > On Tuesday, October 04, 2016 11:13:36 Manu via Digitalmars-d wrote: > >> I'm feeling John's solution is a little bit simpler. But nice work, > >> thanks! > > > > So, it is. LOL. I'd actually glanced over that post while I was in the > > middle of getting my version to work, and I read it too quickly, because I > > understood that it had just solved the property problem and that it didn't > > work for all cases. I'll have to update my PR. Though his code does make > > the mistake of doing > > > > mixin(`alias mem = T.` ~ member ~ `;`); > > > > rather than doing something like > > > > alias mem = AliasSeq!(__traits(getMember, T, member))[0]; > > > > which means that there are some cases where it won't work properly. The > > core logic is simpler though, which is definitely a plus. > > Make that change in your PR :) I already updated it and was actually able to make it slightly simpler than John's example (as far as I can tell, FunctionTypeOf is only needed in the case where the address is taken). > I think the PR is important. It's not obvious how to do this, and it's > very useful. I was astonished it's not already there. Yeah. I ran into a need for something similar recently, but my implementation at the time wasn't as thorough, since it just used offsetof to do the check (though in my case, I think that was enough). Getting it completely right is surprisingly difficult. I was also surprised that while we have quite a few __traits for functions, they're severely lacking for variables (e.g. I was looking for the variable equivalent of __traits(isStaticFunction, ...), and there is no such beast). For that matter, even testing whether something is a variable is surprisingly difficult. - Jonathan M Davis
Re: Challenge
On 4 October 2016 at 12:30, Jonathan M Davis via Digitalmars-d wrote: > On Tuesday, October 04, 2016 11:13:36 Manu via Digitalmars-d wrote: >> I'm feeling John's solution is a little bit simpler. But nice work, thanks! > > So, it is. LOL. I'd actually glanced over that post while I was in the > middle of getting my version to work, and I read it too quickly, because I > understood that it had just solved the property problem and that it didn't > work for all cases. I'll have to update my PR. Though his code does make the > mistake of doing > > mixin(`alias mem = T.` ~ member ~ `;`); > > rather than doing something like > > alias mem = AliasSeq!(__traits(getMember, T, member))[0]; > > which means that there are some cases where it won't work properly. The core > logic is simpler though, which is definitely a plus. Make that change in your PR :) I think the PR is important. It's not obvious how to do this, and it's very useful. I was astonished it's not already there.
Re: Challenge
On Tuesday, October 04, 2016 11:13:36 Manu via Digitalmars-d wrote: > I'm feeling John's solution is a little bit simpler. But nice work, thanks! So, it is. LOL. I'd actually glanced over that post while I was in the middle of getting my version to work, and I read it too quickly, because I understood that it had just solved the property problem and that it didn't work for all cases. I'll have to update my PR. Though his code does make the mistake of doing mixin(`alias mem = T.` ~ member ~ `;`); rather than doing something like alias mem = AliasSeq!(__traits(getMember, T, member))[0]; which means that there are some cases where it won't work properly. The core logic is simpler though, which is definitely a plus. - Jonathan M Davis
Re: Challenge
On 4 October 2016 at 05:01, Jonathan M Davis via Digitalmars-d
wrote:
> On Monday, October 03, 2016 11:13:52 Jonathan M Davis via Digitalmars-d wrote:
>> template isStaticMember(T, string member)
>> {
>> static if (!__traits(hasMember, T, member))
>> enum bool isStaticMember = false;
>> else
>> {
>> import std.meta : AliasSeq;
>> import std.traits : FunctionTypeOf;
>> alias sym = AliasSeq!(__traits(getMember, T, member))[0];
>>
>> static if (__traits(isStaticFunction, sym))
>> enum bool isStaticMember = true;
>> else static if (is(FunctionTypeOf!sym == function) &&
>> is(FunctionTypeOf!(typeof(&sym)) == function))
>> {
>> enum bool isStaticMember = false;
>> }
>> else
>> {
>> enum bool isStaticMember = !__traits(compiles, sym.offsetof) &&
>>__traits(compiles, &sym);
>> }
>> }
>> }
>
> Well, since I took the time to write it, I created a PR for it:
>
> https://github.com/dlang/phobos/pull/4834
>
> So, if anyone sees problems with my implementation, go poke holes in it.
>
> - Jonathan M Davis
>
I'm feeling John's solution is a little bit simpler. But nice work, thanks!
Re: Challenge
On 4 October 2016 at 00:25, John Colvin via Digitalmars-d
wrote:
> On Monday, 3 October 2016 at 13:19:19 UTC, Manu wrote:
>>
>> Fill in the blank...
>> I'm having a really hard time with this. I've made it work with a
>> mountain of code, and I want to see what others come up with...
>
>
> template isStaticMember(T, string member)
> {
> mixin(`alias mem = T.` ~ member ~ `;`);
> import std.traits : FunctionTypeOf;
> static if (is(FunctionTypeOf!mem == function) &&
> is(FunctionTypeOf!(typeof(&mem)) == function))
> enum bool isStaticMember = __traits(isStaticFunction, mem);
> else
> enum bool isStaticMember = is(typeof(&mem));
> }
>
> Basically, using FunctionTypeOf catches @property functions (which just
> typeof wouldn't), but it also catches member variables with function types,
> so we need the second FunctionTypeOf to see if it's still a function when
> you take its address (true for member functions, including @property
> functions, not true for member variables with function types).
>
> Everything else is just "can you take the address of this".
Very nice. This is the quality of solution I was looking for! 3 Significant LOC.
I knew a simple solution must exist. I didn't think of FunctionTypeOf.
Re: Challenge
On Monday, October 03, 2016 11:13:52 Jonathan M Davis via Digitalmars-d wrote:
> template isStaticMember(T, string member)
> {
> static if (!__traits(hasMember, T, member))
> enum bool isStaticMember = false;
> else
> {
> import std.meta : AliasSeq;
> import std.traits : FunctionTypeOf;
> alias sym = AliasSeq!(__traits(getMember, T, member))[0];
>
> static if (__traits(isStaticFunction, sym))
> enum bool isStaticMember = true;
> else static if (is(FunctionTypeOf!sym == function) &&
> is(FunctionTypeOf!(typeof(&sym)) == function))
> {
> enum bool isStaticMember = false;
> }
> else
> {
> enum bool isStaticMember = !__traits(compiles, sym.offsetof) &&
>__traits(compiles, &sym);
> }
> }
> }
Well, since I took the time to write it, I created a PR for it:
https://github.com/dlang/phobos/pull/4834
So, if anyone sees problems with my implementation, go poke holes in it.
- Jonathan M Davis
Re: Challenge
On 10/03/2016 07:41 AM, Seb wrote: On Monday, 3 October 2016 at 13:19:19 UTC, Manu wrote: Fill in the blank... I'm having a really hard time with this. I've made it work with a mountain of code, and I want to see what others come up with... If you succeed, put it in std.traits! Recommend, use latest DMD nightly. I find differences with latest nightly vs release. See also: http://stackoverflow.com/questions/39430684/check-if-class-member-is-static Appeared on dlang forum as well: :) http://forum.dlang.org/post/nni8lp$1ihk$1...@digitalmars.com Ali
Re: Challenge
On Monday, October 03, 2016 08:38:22 Jonathan M Davis via Digitalmars-d wrote:
> On Monday, October 03, 2016 23:19:19 Manu via Digitalmars-d wrote:
> > Fill in the blank...
> > I'm having a really hard time with this. I've made it work with a
> > mountain of code, and I want to see what others come up with...
>
> It's certainly possible that this misses something, but it passes all of
> your test cases:
>
> template isStaticMember(T, string member)
> {
> static if(!__traits(hasMember, T, member))
> enum bool isStaticMember = false;
> else
> {
> import std.meta : AliasSeq;
> import std.traits : FunctionTypeOf;
> alias sym = AliasSeq!(__traits(getMember, T, member))[0];
> static if(__traits(isStaticFunction, sym))
> enum bool isStaticMember = true;
> else static if(is(FunctionTypeOf!sym == function) &&
>is(FunctionTypeOf!(typeof(&sym)) == function))
> {
> enum bool isStaticMember = false;
> }
> else
> {
> enum bool isStaticMember = !__traits(compiles, sym.offsetof) &&
>!is(sym == enum) &&
>!is(sym == class) &&
>!is(sym == struct) &&
>__traits(compiles, &sym);
> }
> }
> }
Actually, it can be reduced even further:
template isStaticMember(T, string member)
{
static if (!__traits(hasMember, T, member))
enum bool isStaticMember = false;
else
{
import std.meta : AliasSeq;
import std.traits : FunctionTypeOf;
alias sym = AliasSeq!(__traits(getMember, T, member))[0];
static if (__traits(isStaticFunction, sym))
enum bool isStaticMember = true;
else static if (is(FunctionTypeOf!sym == function) &&
is(FunctionTypeOf!(typeof(&sym)) == function))
{
enum bool isStaticMember = false;
}
else
{
enum bool isStaticMember = !__traits(compiles, sym.offsetof) &&
__traits(compiles, &sym);
}
}
}
Checking for the address makes it unnecessary to check for enums, classes,
or structs.
- Jonathan M Davis
Re: Challenge
On Monday, October 03, 2016 23:19:19 Manu via Digitalmars-d wrote:
> Fill in the blank...
> I'm having a really hard time with this. I've made it work with a
> mountain of code, and I want to see what others come up with...
It's certainly possible that this misses something, but it passes all of
your test cases:
template isStaticMember(T, string member)
{
static if(!__traits(hasMember, T, member))
enum bool isStaticMember = false;
else
{
import std.meta : AliasSeq;
import std.traits : FunctionTypeOf;
alias sym = AliasSeq!(__traits(getMember, T, member))[0];
static if(__traits(isStaticFunction, sym))
enum bool isStaticMember = true;
else static if(is(FunctionTypeOf!sym == function) &&
is(FunctionTypeOf!(typeof(&sym)) == function))
{
enum bool isStaticMember = false;
}
else
{
enum bool isStaticMember = !__traits(compiles, sym.offsetof) &&
!is(sym == enum) &&
!is(sym == class) &&
!is(sym == struct) &&
__traits(compiles, &sym);
}
}
}
- Jonathan M Davis
Re: Challenge
On Monday, October 03, 2016 23:19:19 Manu via Digitalmars-d wrote:
> Fill in the blank...
> I'm having a really hard time with this. I've made it work with a
> mountain of code, and I want to see what others come up with...
>
> If you succeed, put it in std.traits!
>
> Recommend, use latest DMD nightly. I find differences with latest
> nightly vs release.
>
>
> --- template isStaticMember(T, string member)
> {
> enum bool isStaticMember = [code goes here];
> }
>
>
> struct S
> {
> enum X = 10;
> enum Y
> {
> i = 10
> }
> struct S {}
> class C {}
>
> static int x = 0;
> __gshared int y = 0;
> static void f() {}
> static void f2() pure nothrow @nogc @safe {}
>
> shared void g() {}
>
> static void function() fp;
> __gshared void function() gfp;
> void function() fpm;
>
> void m() {}
> final void m2() const pure nothrow @nogc @safe {}
>
> inout(int) iom() inout { return 10; }
> static inout(int) iosf(inout int x) { return x; }
>
> @property int p() { return 10; }
> static @property int sp() { return 10; }
> }
>
> class C
> {
> enum X = 10;
> enum Y
> {
> i = 10
> }
> struct S {}
> class C {}
>
> static int x = 0;
> __gshared int y = 0;
> static void f() {}
> static void f2() pure nothrow @nogc @safe {}
>
> shared void g() {}
>
> static void function() fp;
> __gshared void function() gfp;
> void function() fpm;
>
> void m() {}
> final void m2() const pure nothrow @nogc @safe {}
>
> inout(int) iom() inout { return 10; }
> static inout(int) iosf(inout int x) { return x; }
>
> @property int p() { return 10; }
> static @property int sp() { return 10; }
> }
>
> static assert(!isStaticMember!(S, "X"), "!");
> static assert(!isStaticMember!(S, "Y"), "!");
> static assert(!isStaticMember!(S, "Y.i"), "!");
> static assert(!isStaticMember!(S, "S"), "!");
> static assert(!isStaticMember!(S, "C"), "!");
> static assert( isStaticMember!(S, "x"), "!");
> static assert( isStaticMember!(S, "y"), "!");
> static assert( isStaticMember!(S, "f"), "!");
> static assert( isStaticMember!(S, "f2"), "!");
> static assert(!isStaticMember!(S, "g"), "!");
> static assert( isStaticMember!(S, "fp"), "!");
> static assert( isStaticMember!(S, "gfp"), "!");
> static assert(!isStaticMember!(S, "fpm"), "!");
> static assert(!isStaticMember!(S, "m"), "!");
> static assert(!isStaticMember!(S, "m2"), "!");
> static assert(!isStaticMember!(S, "iom"), "!");
> static assert( isStaticMember!(S, "iosm"), "!");
> static assert(!isStaticMember!(S, "p"), "!");
> static assert( isStaticMember!(S, "sp"), "!");
>
> static assert(!isStaticMember!(C, "X"), "!");
> static assert(!isStaticMember!(C, "Y"), "!");
> static assert(!isStaticMember!(C, "Y.i"), "!");
> static assert(!isStaticMember!(C, "S"), "!");
> static assert(!isStaticMember!(C, "C"), "!");
> static assert( isStaticMember!(C, "x"), "!");
> static assert( isStaticMember!(C, "y"), "!");
> static assert( isStaticMember!(C, "f"), "!");
> static assert( isStaticMember!(C, "f2"), "!");
> static assert(!isStaticMember!(C, "g"), "!");
> static assert( isStaticMember!(C, "fp"), "!");
> static assert( isStaticMember!(C, "gfp"), "!");
> static assert(!isStaticMember!(C, "fpm"), "!");
> static assert(!isStaticMember!(C, "m"), "!");
> static assert(!isStaticMember!(C, "m2"), "!");
> static assert(!isStaticMember!(C, "iom"), "!");
> static assert( isStaticMember!(C, "iosm"), "!");
> static assert(!isStaticMember!(C, "p"), "!");
> static assert( isStaticMember!(C, "sp"), "!");
I would point out that iosm is missing from both the struct and the class,
so it can't be true for isStaticMember. I assume that you meant for it to be
iosf, which _is_ declared?
- Jonathan M Davis
Re: Challenge
On Monday, 3 October 2016 at 13:19:19 UTC, Manu wrote: Fill in the blank... I'm having a really hard time with this. I've made it work with a mountain of code, and I want to see what others come up with... If you succeed, put it in std.traits! Recommend, use latest DMD nightly. I find differences with latest nightly vs release. See also: http://stackoverflow.com/questions/39430684/check-if-class-member-is-static
Re: Challenge
On 3 October 2016 at 23:48, Manu wrote:
> On 3 October 2016 at 23:41, Manu wrote:
>> I'm finding this rather annoying:
>>
>> struct S
>> {
>> static @property int p() { return 10; }
>> }
>>
>> pragma(msg, typeof(&S.p)); // prints: int function() @property
>> pragma(msg, is(typeof(&S.p) == function)); // prints: false
>>
>> It looks like a function... but I can't identify it as a function!
>
> I guess that should read: is(typeof(&S.p) == R function(A), R, A...)) ??
Here's a leg-up:
template isStaticMember(T, string member)
{
mixin("alias M = T." ~ member ~ ";");
static if(__traits(compiles, &M))
{
static if(!is(typeof(M) == function))
{
static if(is(typeof(&M) == R function(A), R, A...))
{
import std.traits : functionAttributes, FunctionAttribute;
enum isStaticMember = (functionAttributes!M &
FunctionAttribute.property) && /* distinguish static/non-static
@property somehow */ */;
}
else
enum isStaticMember = true;
}
else
{
enum isStaticMember = __traits(isStaticFunction, M);
}
}
else
enum isStaticMember = false;
}
Re: Challenge
On Monday, 3 October 2016 at 13:19:19 UTC, Manu wrote:
Fill in the blank...
I'm having a really hard time with this. I've made it work with
a
mountain of code, and I want to see what others come up with...
template isStaticMember(T, string member)
{
mixin(`alias mem = T.` ~ member ~ `;`);
import std.traits : FunctionTypeOf;
static if (is(FunctionTypeOf!mem == function) &&
is(FunctionTypeOf!(typeof(&mem)) == function))
enum bool isStaticMember = __traits(isStaticFunction,
mem);
else
enum bool isStaticMember = is(typeof(&mem));
}
Basically, using FunctionTypeOf catches @property functions
(which just typeof wouldn't), but it also catches member
variables with function types, so we need the second
FunctionTypeOf to see if it's still a function when you take its
address (true for member functions, including @property
functions, not true for member variables with function types).
Everything else is just "can you take the address of this".
Re: Challenge
On Monday, 3 October 2016 at 13:19:19 UTC, Manu wrote:
Fill in the blank...
I'm having a really hard time with this. I've made it work with
a
mountain of code, and I want to see what others come up with...
[...]
Dere's a typo
static assert( isStaticMember!(S, "iosm"), "!");
Should be iosf
Easy:
template isStaticMember(T, string member)
{
static if(__traits(compiles, &__traits(getMember, T, member)))
{
static if(is(FunctionTypeOf!(__traits(getMember, T, member)) ==
function))
{
enum isStaticMember = isFunctionPointer!(__traits(getMember,
T, member)) || isDelegate!(__traits(getMember, T, member)) ||
__traits(isStaticFunction, __traits(getMember, T, member));
}
else
{
enum isStaticMember = true;//!is(typeof(__traits(getMember, T,
member).offsetof));
}
}
else
{
enum isStaticMember = false;
}
}
Re: Challenge
On Monday, 3 October 2016 at 13:41:13 UTC, Manu wrote:
I'm finding this rather annoying:
struct S
{
static @property int p() { return 10; }
}
pragma(msg, typeof(&S.p)); // prints: int function() @property
pragma(msg, is(typeof(&S.p) == function)); // prints: false
It looks like a function... but I can't identify it as a
function!
https://dlang.org/phobos/std_traits.html#isSomeFunction ?
Re: Challenge
On 3 October 2016 at 23:50, John Colvin via Digitalmars-d
wrote:
> On Monday, 3 October 2016 at 13:41:13 UTC, Manu wrote:
>>
>> I'm finding this rather annoying:
>>
>> struct S
>> {
>> static @property int p() { return 10; }
>> }
>>
>> pragma(msg, typeof(&S.p)); // prints: int function() @property
>> pragma(msg, is(typeof(&S.p) == function)); // prints: false
>>
>> It looks like a function... but I can't identify it as a function!
>
>
> The problem is that function pointers in "is" expressions don't match
> "function" or "delegate".
>
> static assert (is(void delegate() == delegate)); //passes
> static assert (is(void function() == function)); //fails
> static assert (is(void function() == delegate)); //fails
>
> Bug report?
Nar, I just forgot about this well-known edge. 'function' means
something different in is(); it means a proper-function, *not* a
function pointer. if(X == R function(A), R, A...) will test for
function pointers.
It's still hard though, @property's are hard to detect, and I am
really struggling to distinguish between static and non-static
properties without testing for assignments, which is terrible.
Re: Challenge
On Monday, 3 October 2016 at 13:50:26 UTC, John Colvin wrote: The problem is that function pointers in "is" expressions don't match "function" or "delegate". static assert (is(void delegate() == delegate)); //passes static assert (is(void function() == function)); //fails static assert (is(void function() == delegate)); //fails Bug report? Note that there is at least some code that relies on current behavior to distinguish delegate/function fields from method declarations in aggregates.
Re: Challenge
On Monday, 3 October 2016 at 13:41:13 UTC, Manu wrote:
I'm finding this rather annoying:
struct S
{
static @property int p() { return 10; }
}
pragma(msg, typeof(&S.p)); // prints: int function() @property
pragma(msg, is(typeof(&S.p) == function)); // prints: false
It looks like a function... but I can't identify it as a
function!
It works if both:
a) you remove @property
b) you don't convert it to function pointer
struct S
{
static int p() { return 10; }
}
pragma(msg, is(typeof(S.p) == function); // true
Sadly `is(X == function)` is very obscure and confusing because
it doesn't do what one may expect it to do. In current form it
can only be used if something is a function declaration,
everything else is `false`. It is not even possible to manually
express a type which will pass `is(T == function)`, you can only
get `true` by applying `typeof` to existing function declaration.
And @property screws it because the only current effect of
property is exactly changing result of `typeof(propertyFoo)` from
function type to result type.
Re: Challenge
On 3 October 2016 at 23:41, Manu wrote:
> I'm finding this rather annoying:
>
> struct S
> {
> static @property int p() { return 10; }
> }
>
> pragma(msg, typeof(&S.p)); // prints: int function() @property
> pragma(msg, is(typeof(&S.p) == function)); // prints: false
>
> It looks like a function... but I can't identify it as a function!
I guess that should read: is(typeof(&S.p) == R function(A), R, A...)) ??
Re: Challenge
On Monday, 3 October 2016 at 13:41:13 UTC, Manu wrote:
I'm finding this rather annoying:
struct S
{
static @property int p() { return 10; }
}
pragma(msg, typeof(&S.p)); // prints: int function() @property
pragma(msg, is(typeof(&S.p) == function)); // prints: false
It looks like a function... but I can't identify it as a
function!
The problem is that function pointers in "is" expressions don't
match "function" or "delegate".
static assert (is(void delegate() == delegate)); //passes
static assert (is(void function() == function)); //fails
static assert (is(void function() == delegate)); //fails
Bug report?
Re: Challenge
On Monday, 3 October 2016 at 13:19:19 UTC, Manu wrote:
Fill in the blank...
I'm having a really hard time with this. I've made it work with
a
mountain of code, and I want to see what others come up with...
If you succeed, put it in std.traits!
Pretty easy:
template isStaticMember(T, string member)
{
enum bool isStaticMember =
!(member=="X" || member=="Y" || member=="Y.i" || member=="S"
|| member=="C" ||
member=="g" || member=="fpm" || member=="m" || member=="m2" ||
member=="iom" || member=="p");
}
Ok, I'm joking.
Re: Challenge
I'm finding this rather annoying:
struct S
{
static @property int p() { return 10; }
}
pragma(msg, typeof(&S.p)); // prints: int function() @property
pragma(msg, is(typeof(&S.p) == function)); // prints: false
It looks like a function... but I can't identify it as a function!
Challenge
Fill in the blank...
I'm having a really hard time with this. I've made it work with a
mountain of code, and I want to see what others come up with...
If you succeed, put it in std.traits!
Recommend, use latest DMD nightly. I find differences with latest
nightly vs release.
---
template isStaticMember(T, string member)
{
enum bool isStaticMember = [code goes here];
}
struct S
{
enum X = 10;
enum Y
{
i = 10
}
struct S {}
class C {}
static int x = 0;
__gshared int y = 0;
static void f() {}
static void f2() pure nothrow @nogc @safe {}
shared void g() {}
static void function() fp;
__gshared void function() gfp;
void function() fpm;
void m() {}
final void m2() const pure nothrow @nogc @safe {}
inout(int) iom() inout { return 10; }
static inout(int) iosf(inout int x) { return x; }
@property int p() { return 10; }
static @property int sp() { return 10; }
}
class C
{
enum X = 10;
enum Y
{
i = 10
}
struct S {}
class C {}
static int x = 0;
__gshared int y = 0;
static void f() {}
static void f2() pure nothrow @nogc @safe {}
shared void g() {}
static void function() fp;
__gshared void function() gfp;
void function() fpm;
void m() {}
final void m2() const pure nothrow @nogc @safe {}
inout(int) iom() inout { return 10; }
static inout(int) iosf(inout int x) { return x; }
@property int p() { return 10; }
static @property int sp() { return 10; }
}
static assert(!isStaticMember!(S, "X"), "!");
static assert(!isStaticMember!(S, "Y"), "!");
static assert(!isStaticMember!(S, "Y.i"), "!");
static assert(!isStaticMember!(S, "S"), "!");
static assert(!isStaticMember!(S, "C"), "!");
static assert( isStaticMember!(S, "x"), "!");
static assert( isStaticMember!(S, "y"), "!");
static assert( isStaticMember!(S, "f"), "!");
static assert( isStaticMember!(S, "f2"), "!");
static assert(!isStaticMember!(S, "g"), "!");
static assert( isStaticMember!(S, "fp"), "!");
static assert( isStaticMember!(S, "gfp"), "!");
static assert(!isStaticMember!(S, "fpm"), "!");
static assert(!isStaticMember!(S, "m"), "!");
static assert(!isStaticMember!(S, "m2"), "!");
static assert(!isStaticMember!(S, "iom"), "!");
static assert( isStaticMember!(S, "iosm"), "!");
static assert(!isStaticMember!(S, "p"), "!");
static assert( isStaticMember!(S, "sp"), "!");
static assert(!isStaticMember!(C, "X"), "!");
static assert(!isStaticMember!(C, "Y"), "!");
static assert(!isStaticMember!(C, "Y.i"), "!");
static assert(!isStaticMember!(C, "S"), "!");
static assert(!isStaticMember!(C, "C"), "!");
static assert( isStaticMember!(C, "x"), "!");
static assert( isStaticMember!(C, "y"), "!");
static assert( isStaticMember!(C, "f"), "!");
static assert( isStaticMember!(C, "f2"), "!");
static assert(!isStaticMember!(C, "g"), "!");
static assert( isStaticMember!(C, "fp"), "!");
static assert( isStaticMember!(C, "gfp"), "!");
static assert(!isStaticMember!(C, "fpm"), "!");
static assert(!isStaticMember!(C, "m"), "!");
static assert(!isStaticMember!(C, "m2"), "!");
static assert(!isStaticMember!(C, "iom"), "!");
static assert( isStaticMember!(C, "iosm"), "!");
static assert(!isStaticMember!(C, "p"), "!");
static assert( isStaticMember!(C, "sp"), "!");
Re: Challenge: fair partition function
On Monday, 8 February 2016 at 23:25:00 UTC, Andrei Alexandrescu
wrote:
Consider defining a function that partitions a range around a
given index like this:
size_t pivotPartition(alias less = (a, b) => a < b, Range)
(Range r, size_t pivot);
Returns x, one of the the indexes that r[pivot] would have if r
were sorted. Also, r[0 .. x] contains stuff no greater than
r[x] and r[x + 1 .. $] contains stuff no less than r[x].
The challenge is to implement such a function with fairness: if
several elements are equal to r[pivot], return the index
closest to r.length / 2.
The function should be efficient, minimize calls to less and
swap, etc. A variant that is efficient but does not implement
fairness is below.
...
Ultimately, I think you're going to have to perform two
comparisons on *some* elements to check for equality. I thought
of a few tricks which may or may not help.
(1) Keep your code as is and add a final pass to count the number
of elements. However, you only need to scan the larger partition
since it contains the index (r.length / 2) and you're trying to
move closer to that point. The elements in the smaller partition
can simply be ignored.
(2) You may have code which looks something like this:
if(less(e, pivot)){ /+ less than +/ }
else if(less(pivot, e)){ /+ greater than +/ }
else{ /+ equal to +/ }}
This is a big win if most of the elements are less than the
pivot, but also a big loss if most of the elements are greater
than the pivot. A simple trick is to repeat the code twice but
swap the order of comparisons so you get:
if(less(pivot, e)){ /+ greater than +/ }
else if(less(e, pivot)){ /+ less than +/ }
else{ /+ equal to +/ }}
This will place us closer to an average 1.5 comparisons per
element which is better than (1).
(3) Similar to (2) except you only compare each element once so
you're not checking for equality. You're simply alternating
between checking if (e < pivot) or if (pivot < e). So the code
may look something like this:
if(less(pivot, e)){ less }
else{ greater or equal }
if(less(e, pivot)){ greater }
else{ less or equal }
From this, you can group the elements into four partitions:
[LE L G GE]
So you have elements which are definitely less than or greater
than the pivot but also some elements which *may* be equal to the
pivot. Combine this with the first trick (1) and you only have to
scan LE or GE for equality but not both. This is putting us
closer to an average 1.25 comparisons per element but a 4-way
partition would also require much more work.
Challenge: fair partition function
Consider defining a function that partitions a range around a given
index like this:
size_t pivotPartition(alias less = (a, b) => a < b, Range)
(Range r, size_t pivot);
Returns x, one of the the indexes that r[pivot] would have if r were
sorted. Also, r[0 .. x] contains stuff no greater than r[x] and r[x + 1
.. $] contains stuff no less than r[x].
The challenge is to implement such a function with fairness: if several
elements are equal to r[pivot], return the index closest to r.length / 2.
The function should be efficient, minimize calls to less and swap, etc.
A variant that is efficient but does not implement fairness is below.
Andrei
size_t pivotPartition(alias less = (a, b) => a < b, Range)
(Range r, size_t pivot)
{
assert(pivot < r.length || r.length == 0 && pivot == 0);
if (r.length <= 1) return 0;
import std.algorithm : swapAt;
r.swapAt(pivot, 0);
size_t lo = 1, hi = r.length - 1;
loop: for (;;)
{
for (;; ++lo)
{
if (lo > hi) break loop;
if (less(r[0], r[lo])) break;
}
// found the left bound
assert(lo <= hi);
for (;; --hi)
{
if (lo == hi) break loop;
if (less(r[hi], r[0])) break;
}
// found the right bound, swap & make progress
r.swapAt(lo++, hi--);
}
--lo;
r.swapAt(lo, 0);
return lo;
}
Re: Challenge
On Sunday 30 August 2015 16:43, rsw0x wrote: > Is there any reason that closure in this particular example can't > be created on the stack? Seems a bit weird. It may be possible to store it on the stack somehow, or as part of the map struct. I don't know. The point is, that's not what happens. It goes on the GC heap, breaking @nogc.
Re: Challenge
On Sunday, 30 August 2015 at 13:36:45 UTC, anonymous wrote: On Sunday 30 August 2015 12:21, rsw0x wrote: [...] I think this shouldn't compile and it only does so because of issue 14771. https://issues.dlang.org/show_bug.cgi?id=14771 The delegate in foo uses a local variable and it's returned from the function, so it needs a closure. Where does the closure go if not on the GC heap? See also this Learn thread about how to call map with a delegate in a @nogc function: http://forum.dlang.org/post/kpwbtskhnkkiwkdsf...@forum.dlang.org Ali Çehreli's solution there may or may not actually be @nogc, but I'm afraid it relies on issue 14771 any way: http://forum.dlang.org/post/mqr506$10kf$1...@digitalmars.com Is there any reason that closure in this particular example can't be created on the stack? Seems a bit weird.
Re: Challenge
On Sunday 30 August 2015 12:21, rsw0x wrote:
> import std.algorithm, std.range;
>
> auto foo(R)(R a, immutable int b)
> {
> return a.map!(x => x + b);
> }
>
> @nogc @safe unittest
> {
> int[3] test = [1,2,3];
>
> assert(test[].foo(3).equal(only(4,5,6)));
> }
>
> does this count?
I think this shouldn't compile and it only does so because of issue 14771.
https://issues.dlang.org/show_bug.cgi?id=14771
The delegate in foo uses a local variable and it's returned from the
function, so it needs a closure. Where does the closure go if not on the GC
heap?
See also this Learn thread about how to call map with a delegate in a @nogc
function:
http://forum.dlang.org/post/kpwbtskhnkkiwkdsf...@forum.dlang.org
Ali Çehreli's solution there may or may not actually be @nogc, but I'm
afraid it relies on issue 14771 any way:
http://forum.dlang.org/post/mqr506$10kf$1...@digitalmars.com
Re: Challenge
On Sunday, 30 August 2015 at 11:21:34 UTC, Russel Winder wrote: On Sun, 2015-08-30 at 10:38 +, John Colvin via Digitalmars-d wrote: On Sunday, 30 August 2015 at 10:15:14 UTC, John Colvin wrote: > [...] Ok, so now I feel stupid. Not only was the unittest I gave above broken anyway, I realised what my underlying problem was within minutes of posting... So what was the problem? Carry on, nothing to see here... See above… https://issues.dlang.org/show_bug.cgi?id=14982 was confusing me.
Re: Challenge
On Sun, 2015-08-30 at 10:38 +, John Colvin via Digitalmars-d wrote:
> On Sunday, 30 August 2015 at 10:15:14 UTC, John Colvin wrote:
> > import std.algorithm, std.range;
> >
> > auto foo(R)(R a, immutable int b)
> > {
> > return a.map!(x => x + b);
> > }
> >
> > unittest @nogc @safe
> > {
> > int[] test = [1,2,3];
> >
> > assert(test.foo(3).equal(only(4,5,6)));
> > }
> >
> > Challenge: reimplement `foo` such that above unittest will
> > compile. No cheating with malloc etc. Bonus points if you don't
> > have to implement a modified version of std.algorithm.map
>
> Ok, so now I feel stupid. Not only was the unittest I gave above
> broken anyway, I realised what my underlying problem was within
> minutes of posting...
So what was the problem?
> Carry on, nothing to see here...
See above…
--
Russel.
=
Dr Russel Winder t: +44 20 7585 2200 voip: sip:russel.win...@ekiga.net
41 Buckmaster Roadm: +44 7770 465 077 xmpp: rus...@winder.org.uk
London SW11 1EN, UK w: www.russel.org.uk skype: russel_winder
Re: Challenge
On Sunday, 30 August 2015 at 10:15:14 UTC, John Colvin wrote:
import std.algorithm, std.range;
auto foo(R)(R a, immutable int b)
{
return a.map!(x => x + b);
}
unittest @nogc @safe
{
int[] test = [1,2,3];
assert(test.foo(3).equal(only(4,5,6)));
}
Challenge: reimplement `foo` such that above unittest will
compile. No cheating with malloc etc. Bonus points if you don't
have to implement a modified version of std.algorithm.map
Ok, so now I feel stupid. Not only was the unittest I gave above
broken anyway, I realised what my underlying problem was within
minutes of posting...
Carry on, nothing to see here...
Re: Challenge
On Sunday, 30 August 2015 at 10:21:20 UTC, rsw0x wrote:
On Sunday, 30 August 2015 at 10:15:14 UTC, John Colvin wrote:
import std.algorithm, std.range;
auto foo(R)(R a, immutable int b)
{
return a.map!(x => x + b);
}
unittest @nogc @safe
{
int[] test = [1,2,3];
assert(test.foo(3).equal(only(4,5,6)));
}
Challenge: reimplement `foo` such that above unittest will
compile. No cheating with malloc etc. Bonus points if you
don't have to implement a modified version of std.algorithm.map
import std.algorithm, std.range;
auto foo(R)(R a, immutable int b)
{
return a.map!(x => x + b);
}
@nogc @safe unittest
{
int[3] test = [1,2,3];
assert(test[].foo(3).equal(only(4,5,6)));
}
does this count?
Oh, I think I see what you were asking. It doesn't compile with
LDC, but it compiles just fine with latest DMD.
hmm
Re: Challenge
On Sunday, 30 August 2015 at 10:15:14 UTC, John Colvin wrote:
import std.algorithm, std.range;
auto foo(R)(R a, immutable int b)
{
return a.map!(x => x + b);
}
unittest @nogc @safe
{
int[] test = [1,2,3];
assert(test.foo(3).equal(only(4,5,6)));
}
Challenge: reimplement `foo` such that above unittest will
compile. No cheating with malloc etc. Bonus points if you don't
have to implement a modified version of std.algorithm.map
import std.algorithm, std.range;
auto foo(R)(R a, immutable int b)
{
return a.map!(x => x + b);
}
@nogc @safe unittest
{
int[3] test = [1,2,3];
assert(test[].foo(3).equal(only(4,5,6)));
}
does this count?
Challenge
import std.algorithm, std.range;
auto foo(R)(R a, immutable int b)
{
return a.map!(x => x + b);
}
unittest @nogc @safe
{
int[] test = [1,2,3];
assert(test.foo(3).equal(only(4,5,6)));
}
Challenge: reimplement `foo` such that above unittest will
compile. No cheating with malloc etc. Bonus points if you don't
have to implement a modified version of std.algorithm.map
Re: Today's programming challenge - How's your Range-Fu ?
On Tuesday, 21 April 2015 at 13:06:22 UTC, JohnnyK wrote: On Monday, 20 April 2015 at 19:24:01 UTC, Panke wrote: On Monday, 20 April 2015 at 18:03:50 UTC, John Colvin wrote: On Monday, 20 April 2015 at 17:48:17 UTC, Panke wrote: To measure the columns needed to print a string, you'll need the number of graphemes. (d|)?string.length gives you the number of code units. Even that's not really true. Why? Doesn't string.length give you the byte count? I was talking about the "you'll need the number of graphemes". s.length returns the number of elements in the slice, which in the case of D's string types gives is the same as the number of code units. I think what you are looking for is string.sizeof? From the D reference .sizeof Returns the array length multiplied by the number of bytes per array element. .length Returns the number of elements in the array. This is a fixed quantity for static arrays. It is of type size_t. That is for static arrays only. .sizeof for slices is just size_t.sizeof + T*.sizeof i.e. 8 on 32 bit, 16 on 64 bit.
Re: Today's programming challenge - How's your Range-Fu ?
On Monday, 20 April 2015 at 19:24:01 UTC, Panke wrote: On Monday, 20 April 2015 at 18:03:50 UTC, John Colvin wrote: On Monday, 20 April 2015 at 17:48:17 UTC, Panke wrote: To measure the columns needed to print a string, you'll need the number of graphemes. (d|)?string.length gives you the number of code units. Even that's not really true. Why? Doesn't string.length give you the byte count? I think what you are looking for is string.sizeof? From the D reference .sizeof Returns the array length multiplied by the number of bytes per array element. .length Returns the number of elements in the array. This is a fixed quantity for static arrays. It is of type size_t. Isn't a string type an array of characters (char[] string UTF-8, wchar[] string UTF-16, and dchar[] string UTF-32) and not arbitrary bytes?
Re: Today's programming challenge - How's your Range-Fu ?
On Monday, 20 April 2015 at 19:24:01 UTC, Panke wrote: On Monday, 20 April 2015 at 18:03:50 UTC, John Colvin wrote: On Monday, 20 April 2015 at 17:48:17 UTC, Panke wrote: To measure the columns needed to print a string, you'll need the number of graphemes. (d|)?string.length gives you the number of code units. Even that's not really true. Why? Doesn't string.length give you the byte count? You'll also need the unicode character display width: Even if the font is monospaced, there are characters (Katakana, Hangul and even in Latin script) with variable width. ABCDEFGH ＡＢＣＤＥＦＧＨ (unicode 0xff21 through 0xff27). If the text above is not correctly displayed on your computer, a Korean console can be viewed here: http://upload.wikimedia.org/wikipedia/commons/1/14/KoreanDOSPrompt.png
Re: Today's programming challenge - How's your Range-Fu ?
On Monday, 20 April 2015 at 18:03:50 UTC, John Colvin wrote: On Monday, 20 April 2015 at 17:48:17 UTC, Panke wrote: To measure the columns needed to print a string, you'll need the number of graphemes. (d|)?string.length gives you the number of code units. Even that's not really true. Why? Doesn't string.length give you the byte count?
Re: Today's programming challenge - How's your Range-Fu ?
On Monday, 20 April 2015 at 17:48:17 UTC, Panke wrote: This can lead to subtle bugs, cf. length of random and e_one. You have to convert everything to dstring to get the "expected" result. However, this is not always desirable. There are three things that you need to be aware of when handling unicode: code units, code points and graphems. This is why I use a helper function that uses byCodePoint and byGrapheme. At least for my use cases it returns the correct length. However, I might think about an alternative version based on the discussion here. In general the length of one guarantees anything about the length of the other, except for utf32, which is a 1:1 mapping between code units and code points. In this thread, we were discussing the relationship between code points and graphemes. You're examples however apply to the relationship between code units and code points. To measure the columns needed to print a string, you'll need the number of graphemes. (d|)?string.length gives you the number of code units. If you normalize a string (in the sequence of characters/codepoints sense, not object.string) to NFC, it will decompose every precomposed character in the string (like é, single codeunit), establish a defined order between the composite characters and then recompose a selected few graphemes (like é). This way é always ends up as a single code unit in NFC. There are dozens of other combinations where you'll still have n:1 mapping between code points and graphemes left after normalization. Example given already in this thread: putting an arrow over an latin letter is typical in math and always more than one codepoint.
