* * *

Author Topic: Volunteers for migrating a nice project to pascal  (Read 1906 times)

apexcol

  • Jr. Member
  • **
  • Posts: 51
Volunteers for migrating a nice project to pascal
« on: January 30, 2018, 10:13:35 am »
Hi, I saw this project primesieve.org and it's so impressive.

I'm finding some volunteers that help to migrate this code written in C++ to pascal, or at least translate the C code, or write FreePascal bindings for primesieve's C API (see http://primesieve.org/api/). Usually it is easier in most languages to write bindings for a C API than for a C++ API.

:)

engkin

  • Hero Member
  • *****
  • Posts: 1984
Re: Volunteers for migrating a nice project to pascal
« Reply #1 on: February 13, 2018, 08:33:44 am »
Thanks for bringing this up. I just did a quick test:
Code: Pascal  [Select]
  1. program project1;
  2.  
  3. {$mode objfpc}{$H+}
  4.  
  5. uses
  6.   {$IFDEF UNIX}{$IFDEF UseCThreads}
  7.   cthreads,
  8.   {$ENDIF}{$ENDIF}
  9.   Classes, sysutils
  10.   { you can add units after this };
  11.  
  12. const
  13.   PrimeSieveLib='primsiev.dll';
  14.  
  15. type
  16.   TPrimeType = (
  17.   //* Generate primes of short type
  18.   SHORT_PRIMES,
  19.   //* Generate primes of unsigned short type
  20.   USHORT_PRIMES,
  21.   //* Generate primes of int type
  22.   INT_PRIMES,
  23.   //* Generate primes of unsigned int type
  24.   UINT_PRIMES,
  25.   //* Generate primes of long type
  26.   LONG_PRIMES,
  27.   //* Generate primes of unsigned long type
  28.   ULONG_PRIMES,
  29.   //* Generate primes of long long type
  30.   LONGLONG_PRIMES,
  31.   //* Generate primes of unsigned long long type
  32.   ULONGLONG_PRIMES,
  33.   //* Generate primes of int16_t type
  34.   INT16_PRIMES,
  35.   //* Generate primes of uint16_t type
  36.   UINT16_PRIMES,
  37.   //* Generate primes of int32_t type
  38.   INT32_PRIMES,
  39.   //* Generate primes of uint32_t type
  40.   UINT32_PRIMES,
  41.   //* Generate primes of int64_t type
  42.   INT64_PRIMES,
  43.   //* Generate primes of uint64_t type
  44.   UINT64_PRIMES
  45. );
  46.  
  47. function primesieve_version():pchar; cdecl; external PrimeSieveLib;
  48. function primesieve_count_primes(start, stop: UInt64): UInt64; cdecl; external PrimeSieveLib;
  49. function primesieve_parallel_count_primes(start, stop: UInt64): UInt64; cdecl; external PrimeSieveLib;
  50. function primesieve_nth_prime(n,start: uint64): UInt64; cdecl; external PrimeSieveLib;
  51. function primesieve_generate_primes(start, stop: uint64;  size: pinteger; &type: TPrimeType): pointer; cdecl; external PrimeSieveLib;
  52. procedure primesieve_free(primes: pointer); cdecl; external PrimeSieveLib;
  53. function primesieve_generate_n_primes(n, start: uint64; &type: TPrimeType): pointer; cdecl; external PrimeSieveLib;
  54.  
  55.  
  56. procedure Test_CountPrimes;
  57. var
  58.   count: QWord;
  59. begin
  60.   count := primesieve_count_primes(0, 1000);
  61.   writeln('Primes below 1000 = ', count);
  62.  
  63.   // use multi-threading for large intervals
  64.   count := primesieve_parallel_count_primes(0, 1000000000);
  65.   writeln('Primes below 10^9 = ', count);
  66. end;
  67.  
  68. procedure Test_nth_prime(n: uint64);
  69. var
  70.   prime: uint64;
  71. begin
  72.   prime := primesieve_nth_prime(n, 0);
  73.   writeln(n,'th prime = ', prime);
  74. end;
  75.  
  76. procedure Test_store_primes_in_array;
  77. var
  78.   start, stop, n: uint64;
  79.   i, size: integer;
  80.   primes: PInteger;
  81. begin
  82.   start := 0;
  83.   stop := 1000;
  84.  
  85.   // store the primes below 1000
  86.   primes := primesieve_generate_primes(start, stop, @size, INT_PRIMES);
  87.  
  88.   for i := 0 to size-1 do
  89.     writeLn(i,': ', primes[i]);
  90.  
  91.   primesieve_free(primes);
  92.   n := 1000;
  93.  
  94.   // store the first 1000 primes
  95.   primes := primesieve_generate_n_primes(n, start, INT_PRIMES);
  96.  
  97.   for i := 0 to n-1 do
  98.     writeLn(i+1,'\',n,': ', primes[i]);
  99.  
  100.   primesieve_free(primes);
  101. end;
  102.  
  103. begin
  104.   WriteLn('Dll Version: ',primesieve_version);
  105.   Test_CountPrimes;
  106.   Test_nth_prime(1000);
  107.   Test_store_primes_in_array;
  108. end.

The output of the project is:
Quote
Dll Version: 5.7.3
Primes below 1000 = 168
Primes below 10^9 = 50847534
1000th prime = 7919
0: 2
1: 3
2: 5
3: 7
4: 11
5: 13
6: 17
7: 19
8: 23
9: 29
[snip]
164: 977
165: 983
166: 991
167: 997
1\1000: 2
2\1000: 3
3\1000: 5
4\1000: 7
5\1000: 11
6\1000: 13
7\1000: 17
8\1000: 19
9\1000: 23
10\1000: 29
11\1000: 31
12\1000: 37
13\1000: 41
14\1000: 43
15\1000: 47
16\1000: 53
17\1000: 59
18\1000: 61
19\1000: 67
20\1000: 71
21\1000: 73
22\1000: 79
[snip]
994\1000: 7873
995\1000: 7877
996\1000: 7879
997\1000: 7883
998\1000: 7901
999\1000: 7907
1000\1000: 7919

In case someone wants to test, attached is the 32-bit DLL I generated using the original PrimeSieve C++ code version 5.7.3.

Thaddy

  • Hero Member
  • *****
  • Posts: 6130
Re: Volunteers for migrating a nice project to pascal
« Reply #2 on: February 13, 2018, 12:10:35 pm »
Ahummm. Do we need it? This is basic school math and should be just as fast in pure Pascal.
I might not give the answer that you want me to.. Peter Green 1969

taazz

  • Hero Member
  • *****
  • Posts: 5081
Re: Volunteers for migrating a nice project to pascal
« Reply #3 on: February 13, 2018, 12:31:18 pm »
Ahummm. Do we need it? This is basic school math and should be just as fast in pure Pascal.
do we have it? if its so basic then is there any unit that can be used?
Good judgement is the result of experience … Experience is the result of bad judgement.

OS : Windows 7 64 bit
Laz: Lazarus 1.4.4 FPC 2.6.4 i386-win32-win32/win64

rvk

  • Hero Member
  • *****
  • Posts: 3440
Re: Volunteers for migrating a nice project to pascal
« Reply #4 on: February 13, 2018, 12:32:10 pm »
Ahummm. Do we need it? This is basic school math and should be just as fast in pure Pascal.
Hence the question from the topicstarter :)
I'm finding some volunteers that help to migrate this code written in C++ to pascal...

engkin

  • Hero Member
  • *****
  • Posts: 1984
Re: Volunteers for migrating a nice project to pascal
« Reply #5 on: February 21, 2018, 08:14:33 pm »
@Thaddy, I understand your concern. PrimeSieve is limited to UInt64  ;) Still it is lightning fast.

I exported more functions in the attached DLL:
Code: Pascal  [Select]
  1. unit primesieve;
  2.  
  3. {$mode objfpc}{$H+}
  4.  
  5. interface
  6.  
  7. const
  8.   PrimeSieveLib='primsiev.dll';
  9.  
  10. type
  11.   TPrimeType = (
  12.   //* Generate primes of short type
  13.   SHORT_PRIMES,
  14.   //* Generate primes of unsigned short type
  15.   USHORT_PRIMES,
  16.   //* Generate primes of int type
  17.   INT_PRIMES,
  18.   //* Generate primes of unsigned int type
  19.   UINT_PRIMES,
  20.   //* Generate primes of long type
  21.   LONG_PRIMES,
  22.   //* Generate primes of unsigned long type
  23.   ULONG_PRIMES,
  24.   //* Generate primes of long long type
  25.   LONGLONG_PRIMES,
  26.   //* Generate primes of unsigned long long type
  27.   ULONGLONG_PRIMES,
  28.   //* Generate primes of int16_t type
  29.   INT16_PRIMES,
  30.   //* Generate primes of uint16_t type
  31.   UINT16_PRIMES,
  32.   //* Generate primes of int32_t type
  33.   INT32_PRIMES,
  34.   //* Generate primes of uint32_t type
  35.   UINT32_PRIMES,
  36.   //* Generate primes of int64_t type
  37.   INT64_PRIMES,
  38.   //* Generate primes of uint64 type
  39.   UINT64_PRIMES
  40. );
  41.  
  42. TPrimesieve_callback = procedure (prime: uint64); cdecl;
  43.  
  44. function primesieve_version():pchar; cdecl; external PrimeSieveLib;
  45. function primesieve_count_primes(start, stop: UInt64): UInt64; cdecl; external PrimeSieveLib;
  46. function primesieve_parallel_count_primes(start, stop: UInt64): UInt64; cdecl; external PrimeSieveLib;
  47. function primesieve_nth_prime(n: int64; start: uint64): UInt64; cdecl; external PrimeSieveLib;
  48. function primesieve_generate_primes(start, stop: uint64;  size: pinteger; &type: TPrimeType): pointer; cdecl; external PrimeSieveLib;
  49. procedure primesieve_free(primes: pointer); cdecl; external PrimeSieveLib;
  50. function primesieve_generate_n_primes(n, start: uint64; &type: TPrimeType): pointer; cdecl; external PrimeSieveLib;
  51.  
  52. procedure primesieve_callback_primes(start, stop: uint64; callback: TPrimesieve_callback); cdecl; external PrimeSieveLib;
  53.  
  54.  
  55.  
  56. {$PackRecords C}
  57. type
  58.   primesieve_iterator = record
  59.     i_: PtrInt;
  60.     last_idx_: PtrInt;
  61.     primes_:PUInt64;
  62.     primes_pimpl_:PUInt64;
  63.     start_:uint64;
  64.     stop_:uint64 ;
  65.     stop_hint_:uint64 ;
  66.     tiny_cache_size_:uint64 ;
  67.     is_error_:Integer ;
  68.   end;
  69.   pprimesieve_iterator = ^primesieve_iterator;
  70.  
  71. procedure primesieve_init (var pi: primesieve_iterator); cdecl; external PrimeSieveLib;
  72. procedure primesieve_free_iterator (var pi: primesieve_iterator); cdecl; external PrimeSieveLib;
  73. function primesieve_next_prime (var pi: primesieve_iterator): uint64; cdecl; external PrimeSieveLib;
  74. function primesieve_previous_prime (var pi: primesieve_iterator): uint64; cdecl; external PrimeSieveLib;
  75. procedure primesieve_skipto(var pi: primesieve_iterator; start, stop_hint: uint64); cdecl; external PrimeSieveLib;
  76.  
  77.  
  78. { Get the current set sieve size in kilobytes }
  79. function primesieve_get_sieve_size(): integer; cdecl; external PrimeSieveLib;
  80.  
  81. { Get the current set number of threads }
  82. function primesieve_get_num_threads(): integer; cdecl; external PrimeSieveLib;
  83.  
  84. {
  85.  * Returns the largest valid stop number for primesieve.
  86.  * @return 2^64-1 (UINT64_MAX).
  87.  }
  88. function primesieve_get_max_stop(): uint64; cdecl; external PrimeSieveLib;
  89.  
  90. {
  91.  * Set the sieve size in kilobytes.
  92.  * The best sieving performance is achieved with a sieve size of
  93.  * your CPU's L1 data cache size (per core). For sieving >= 10^17 a
  94.  * sieve size of your CPU's L2 cache size sometimes performs
  95.  * better.
  96.  * @param sieve_size Sieve size in kilobytes.
  97.  * @pre   sieve_size >= 1 && <= 2048.
  98.  }
  99. procedure primesieve_set_sieve_size(sieve_size: integer); cdecl; external PrimeSieveLib;
  100.  
  101. {
  102.  * Set the number of threads for use in subsequent
  103.  * primesieve_parallel_* function calls.
  104.  }
  105. procedure primesieve_set_num_threads(num_threads: integer); cdecl; external PrimeSieveLib;
  106.  
  107.  
  108. implementation
  109.  
  110. end.

Project includes some tests.

apexcol

  • Jr. Member
  • **
  • Posts: 51
Re: Volunteers for migrating a nice project to pascal
« Reply #6 on: February 27, 2018, 06:57:00 am »
I could translate the segmented sieve that is on C++.  And the benchmark only without optimizations of the library is faster in Pascal, I don't know why.

Code: Pascal  [Select]
  1. unit Unit1;
  2.  
  3. {$mode objfpc}{$H+}
  4.  
  5. interface
  6.  
  7. uses
  8.   Classes, math, SysUtils, FileUtil, Forms, Controls, Graphics,
  9.   StdCtrls;
  10.  
  11. type
  12.  
  13.   { TForm1 }
  14.  
  15.   TForm1 = class(TForm)
  16.     btnCalculaSieve: TButton;
  17.     Edit1: TEdit;
  18.     Memo1: TMemo;
  19.     Memo2: TMemo;
  20.     procedure btnCalculaSieveClick(Sender: TObject);
  21.   private
  22.     procedure segmented_sieve(const limit: int64);
  23.  
  24.   public
  25.  
  26.   end;
  27.  
  28.   { std_vector }
  29.  
  30.   generic std_vector<T> = class
  31.   type TarrT = array of T;
  32.   strict private
  33.     FItems: TarrT;
  34.     FCount: T;
  35.     function GetItem(aIndex: T): T;
  36.     procedure SetItem(const aIndex: T;const AValue: T);
  37.   public
  38.     procedure Add(const Value: T);
  39.     property Items[aIndex: T]: T read GetItem write SetItem; default;
  40.     property Count: T read FCount;
  41.   end;
  42.  
  43. var
  44.   Form1: TForm1;
  45.  
  46. implementation
  47.  
  48. {$R *.frm}
  49.  
  50. const
  51.   /// Set your CPU's L1 data cache size (in bytes) here
  52.   L1D_CACHE_SIZE : integer = 32768;
  53.   init_count: array [boolean] of byte = (1, 0); // for emulating (limit < 2) ? 0 : 1;
  54.  
  55. { std_vector implementation }
  56.  
  57. function std_vector.GetItem(aIndex: T): T;
  58. begin
  59.   result := FItems[aIndex];
  60. end;
  61.  
  62. procedure std_vector.SetItem(const aIndex: T;const AValue: T);
  63. begin
  64.   if FItems[aIndex] <> aValue then
  65.     FItems[aIndex] := aValue;
  66. end;
  67.  
  68. procedure std_vector.Add(const Value: T);
  69. begin
  70.   inc(FCount);
  71.   SetLength(FItems, FCount);
  72.   FItems[FCount-1] := Value;
  73. end;
  74.  
  75. { TForm1 }
  76.  
  77. procedure TForm1.segmented_sieve(const limit: int64);
  78. var
  79.   sqrt,
  80.   segment_size,
  81.   i, j, k,
  82.   S, N, _high:int64;
  83.   count: int64 = 0;
  84.   _low: int64 = 0;
  85.   is_prime,              /// std::vector<char> is_prime
  86.   sieve: array of byte;  /// std::vector<char> sieve
  87.   primes, // can be TFPList or use TList instead
  88.   _next: specialize std_vector<QWord>;
  89.  
  90. begin
  91.   sqrt := Trunc(System.sqrt(limit));
  92.   segment_size := Max(sqrt, L1D_CACHE_SIZE);
  93.  
  94.   inc(count, init_count[limit < 2]);
  95.   S := 3;
  96.   N := 3;
  97.  
  98.   // generates small primes <= sqrt
  99.   SetLength(is_prime, sqrt);
  100.   //FillByte(is_prime[0], length(is_prime), 1); // Little improvement 3 next lines
  101.   FillWord(is_prime[0], length(is_prime) div 2, $100);
  102.   FillWord(is_prime[0], 2, $101);
  103.   i := 3;
  104.   while (i*i <= sqrt) do begin
  105.     if boolean(is_prime[i]) then begin  
  106.           j := i*i;
  107.           while (j <= sqrt) do begin
  108.             is_prime[j] := 0;
  109.             inc(j,i);
  110.           end;
  111.         end;
  112.         inc(i);
  113.   end;
  114.  
  115.   // vector used to sieve
  116.   SetLength(sieve, segment_size);
  117.   primes := specialize std_vector<longWord>.Create;
  118.   _next := specialize std_vector<longWord>.Create;
  119.  
  120.   while (_low <= limit) do begin
  121.     FillByte(sieve[0], length(sieve), 1);
  122.         // actual segment = interval [_low, _high]
  123.         _high := math.min(_low + segment_size - 1, limit);
  124.         // adds new primes in sieve <= sqrt(_high)
  125.         while (S * S <= _high) do begin
  126.           if boolean(is_prime[S]) then begin
  127.             primes.Add(S);
  128.             _next.Add(integer(S * S - _low));
  129.           end;
  130.           inc(S, 2);
  131.         end;
  132.  
  133.   // sieves the actual segment
  134.     i := 0;
  135.     while (i < primes.Count) do begin
  136.       j := _next[i];
  137.       k := primes[i] * 2;
  138.       while (j < segment_size) do begin
  139.         sieve[j] := 0;
  140.         inc(j,k);//j+=k
  141.       end;
  142.       _next[i] := j - segment_size;
  143.       inc(i);
  144.     end;
  145.  
  146.     while (N <= _high) do begin
  147.       if boolean(sieve[N - _low]) then
  148.         inc(count);
  149.       inc(N, 2);
  150.     end;
  151.     inc(_low, segment_size);//_low += segment_size;
  152.   end;
  153.   Form1.Caption := intToStr(count);
  154.  
  155.   primes.Free;
  156.   _next.Free;
  157. end;
  158. procedure TForm1.btnCalculaSieveClick(Sender: TObject);
  159. var
  160.   lim: Int64;
  161.   DT: QWord;  
  162. begin
  163.   DT := GetTickCount64;
  164.   Caption := 'Calculating...';
  165.   lim := StrToInt(Edit1.Text);
  166.   segmented_sieve(lim);
  167.   DT := GetTickCount64 - DT;
  168.   Caption := Caption + ' : [' + IntToStr(DT) + '] millisecs';
  169. end;
  170.  
  171. end.                
  172.  

I put the C++ code on MinGW and compiled it, and it calculates 1x109 in 5.500 milliseconds in my old laptop, and the Pascal version does the same in 4.911 milliseconds.
« Last Edit: February 27, 2018, 07:32:04 am by apexcol »

engkin

  • Hero Member
  • *****
  • Posts: 1984
Re: Volunteers for migrating a nice project to pascal
« Reply #7 on: February 27, 2018, 08:07:35 pm »
I put the C++ code on MinGW and compiled it, and it calculates 1x109 in 5.500 milliseconds in my old laptop, and the Pascal version does the same in 4.911 milliseconds.

Using time, specially on a laptop, is not accurate. Try CPU cycles instead:
Code: Pascal  [Select]
  1.   function HardwareTicks: Int64; {$AsmMode intel} assembler; asm DW 0310FH end;

engkin

  • Hero Member
  • *****
  • Posts: 1984
Re: Volunteers for migrating a nice project to pascal
« Reply #8 on: March 03, 2018, 04:45:31 am »
I put the C++ code on MinGW and compiled it, and it calculates 1x109 in 5.500 milliseconds in my old laptop, and the Pascal version does the same in 4.911 milliseconds.

I just did this test on my old 32bit laptop.
primesieve-3.6-win32 counted 109 in 700 ms
Your code: 12000 ms
That is ~17 times slower.

I guess your MinGW compilation is not that good?

apexcol

  • Jr. Member
  • **
  • Posts: 51
Re: Volunteers for migrating a nice project to pascal
« Reply #9 on: March 13, 2018, 10:55:56 am »
Dear engkin, if you read well, I said this...

Quote
I could translate the segmented sieve that is on C++.  And the benchmark only without optimizations of the library is faster in Pascal, I don't know why.

WITHOUT OPTIMIZATIONS!!!  Only the segmented part... not the optimized entire project. ;)

and I also tried an intel core i7, and benchmarks are impressive...
« Last Edit: March 13, 2018, 10:57:27 am by apexcol »

 

Recent

Get Lazarus at SourceForge.net. Fast, secure and Free Open Source software downloads Open Hub project report for Lazarus