Rosetta Code

Sieve of Eratosthenes: Difference between revisions

Page Discussion

Sieve of Eratosthenes (view source)

Revision as of 07:56, 4 June 2021

725 bytes removed ,  3 years ago
→‎Hash Table Based Odds-Only Version: Chapel - Updated version check, qualified time...
m (→‎Alternate Odds-Only Bit-Packed Implementation: Chapel - Updated version check, qualified time...)
(→‎Hash Table Based Odds-Only Version: Chapel - Updated version check, qualified time...)
Line 2,594:
<lang chapel>use Time;
 
config const limit = 1000000100000000;
 
type Prime = uint(32);
Line 2,648:
 
<pre>The first 25 primes are: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
Found 784985761455 primes up to 1000000100000000 in 13079020.012 milliseconds.</pre>
 
Time as run using Chapel version 24.1 on an Intel Skylake i5-6500 at 3.6 GHz (turbo, single threaded).
As you can see, this is much slower than the array based versions, and in fact so slow as to be almost useless; this is due to Chapel's current inefficient implementation of hash tables, both as Association Arrays as used here and in the Map standard library (even slower, likely due to extra indirection). In fact, this is about ten times slower than as the Python code from which it was translated due to Python's extremely well optimized hash table implementation as used internally. Also, this does not have the expected O(1) performance as for usual hash table implementations such as the Python code, but gets much slower with increasing range. This slowness is likely partly due to the Associative Array implementation using complex cryptographic hashing algorithms but there is also something extremely wrong in that it misses the amortized O(1) performance!
 
As you can see, this is much slower than the array based versions; this is due in part to Chapel's current somewhat inefficient implementation of hash tables, both as Association Arrays as used here and in the Map standard library. This is somewhat slower than as run in Python as for the code from which it was translated due to Python's extremely well optimized hash table implementation as used internally.
This desperately needs some attention in Chapel!
 
ToAs showan thatalternate it's not reallyto the fault of the language but rather just this partuse of a built-in library, the following code implements a specialized BasePrimesTable that works similarly to the way the Python associative arrays work as to hashing algorithm used (noneno hashing, as the hash values for integers are just themselves) and something similar to the Python method of handling hash table collisions is used:
 
{{works with|Chapel|1.22}}
Line 2,661:
<lang chapel>use Time;
config const limit = 1000000100000000;
type Prime = uint(32);
Line 2,759:
 
<pre>The first 25 primes are: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
Found 784985761455 primes up to 1000000100000000 in 152020.603 milliseconds.</pre>
 
When called with the `--limit=100000000` command line option to the executable file, the following results:
 
{{out}}
 
<pre>The first 25 primes are: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
Found 5761455 primes up to 100000000 in 2591.61 milliseconds.</pre>
 
This last code is quite usable up to a hundred million (as here) or even a billion in a little over ten times the time, but is still slower than the very simple odds-only monolithic array version and is also more complex, although it uses less memory (only for the hash table for the base primes of about eight Kilobytes for sieving to a billion compared to over 60 Megabytes for the monolithic odds-only simple version).
GordonBGood
474

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/39745"