I haven't seen this posted before so apologies if redundant.
A couple days ago this person posted on YouTube this clip: https://www.youtube.com/watch?v=pv4Yq35Chx0.
In the video it was run against Pascal and Ada lost by being 50% slower than Pascal on Prime Sieving. Also shown as 2 orders of magnitude slower than the fastest implementation of that day. See on video at 20:45.
This is the base implementation link: https://github.com/PlummersSoftwareLLC/Primes/blob/drag-race/PrimeAda/solution_1/src/main.adb.
I know it's trivial, and probably click bait on the video person, but this is not a good PR on Ada reputation. The guy said do a better implementation to get a better score. So can Ada implementation do better?

On 07/07/2021 15:21, Richard Iswara wrote:
> I haven't seen this posted before so apologies if redundant.
> A couple days ago this person posted on YouTube this clip: https://www.youtube.com/watch?v=pv4Yq35Chx0.

I watched this finally yesterday as it kept popping up. I started
running the entire project last night as running the Ada one on it's own
didn't do anything. It's still running, It's been on PrimeR all day!

> In the video it was run against Pascal and Ada lost by being 50% slower than Pascal on Prime Sieving. Also shown as 2 orders of magnitude slower than the fastest implementation of that day. See on video at 20:45.
> This is the base implementation link: https://github.com/PlummersSoftwareLLC/Primes/blob/drag-race/PrimeAda/solution_1/src/main.adb.
> I know it's trivial, and probably click bait on the video person, but this is not a good PR on Ada reputation. The guy said do a better implementation to get a better score. So can Ada implementation do better?
>

Don't know as I don't know the algorithm, but I did clone the repo to
look at it. I would be comparing Ada with C, C++, Pascal and any other
compiled language. Not just Pascal.

On Wed, 7 Jul 2021 16:06:46 +0100, "Luke A. Guest"
<laguest@archeia.com> wrote:

>On 07/07/2021 15:21, Richard Iswara wrote:
>> I haven't seen this posted before so apologies if redundant.
>> A couple days ago this person posted on YouTube this clip: https://www.youtube.com/watch?v=pv4Yq35Chx0.
>
>I watched this finally yesterday as it kept popping up. I started
>running the entire project last night as running the Ada one on it's own
>didn't do anything. It's still running, It's been on PrimeR all day!
>
>> In the video it was run against Pascal and Ada lost by being 50% slower than Pascal on Prime Sieving. Also shown as 2 orders of magnitude slower than the fastest implementation of that day. See on video at 20:45.
>> This is the base implementation link: https://github.com/PlummersSoftwareLLC/Primes/blob/drag-race/PrimeAda/solution_1/src/main.adb.
>> I know it's trivial, and probably click bait on the video person, but this is not a good PR on Ada reputation. The guy said do a better implementation to get a better score. So can Ada implementation do better?
>>
>
>Don't know as I don't know the algorithm, but I did clone the repo to
>look at it. I would be comparing Ada with C, C++, Pascal and any other
>compiled language. Not just Pascal.

There are many algorithms to find primes, some are optimized some not.
It makes no sense comparing languages with the same algorithm, I'm
sure every language can be made faster with a language-optimized
prime-finding algorithm.

Doctor Who <doc@tardis.org> writes:

> It makes no sense comparing languages with the same algorithm,

I think it makes little sense to compare languages with _different_
algorithms.

On Wed, 07 Jul 2021 20:21:26 +0100, Simon Wright <simon@pushface.org>
wrote:

>Doctor Who <doc@tardis.org> writes:
>
>> It makes no sense comparing languages with the same algorithm,
>
>I think it makes little sense to compare languages with _different_
>algorithms.

it depends if you are comparing algorithms or comparing languages ...

On 07/07/2021 20:49, Doctor Who wrote:
>> I think it makes little sense to compare languages with _different_
>> algorithms.
>
> it depends if you are comparing algorithms or comparing languages ...
>

It's a comparison of languages using the same algorithm, but you can
also add in other algorithms, just like there are parallel versions.

On Thursday, July 8, 2021 at 2:49:48 AM UTC+7, Doctor Who wrote:
> On Wed, 07 Jul 2021 20:21:26 +0100, Simon Wright <si...@pushface.org>
> wrote:
> >Doctor Who <d...@tardis.org> writes:
> >
> >> It makes no sense comparing languages with the same algorithm,
> >
> >I think it makes little sense to compare languages with _different_
> >algorithms.
> it depends if you are comparing algorithms or comparing languages ...
It is supposed to be a basic Sieve of Erastosthenes searching primes under 1 million.
Odd number search only, can be multi threaded and skip ahead. See the rules at: https://github.com/plummerssoftwarellc/Primes/blob/drag-race/CONTRIBUTING.md#rules.
Indirectly it is a comparison of implementation and tools benchmarking. Looking at the gpr file, there is no compile switch used, not even an "-o2" switch.

On 7/8/21 5:46 AM, Richard Iswara wrote:
> Indirectly it is a comparison of implementation and tools benchmarking. Looking at the gpr file, there is no compile switch used, not even an "-o2" switch.

Compiling with -gnatp -O3 would undoubtedly speed it up (suppressing checks is
justified since execution with checks active shows that no checks fail).

Looking casually at the code, the map could be replaced by a constant, as
Sieve_Size is hard coded to 1,000,000, and the filling of the map is included in
the timing. The calculation of the square root of 1,000,000 could be replaced by
a constant. The array of Boolean could be constrained to 3 .. Sieve_Size. The
function that simply returns (others => True) could be replaced by the
aggregate, though optimization will probably do that. Long_Long_Integer could be
replaced by a type with range 0 .. 2 ** 31 - 1, though I don't know if that
would have any effect. The first inner loop in the sieve algorithm could be
eliminated, in which case the initialization of Num could also be removed.

--
Jeff Carter
"My legs are gray, my ears are gnarled, my eyes are old and bent."
Monty Python's Life of Brian
81

On 2021-07-08 10:20, Jeffrey R. Carter wrote:
> On 7/8/21 5:46 AM, Richard Iswara wrote:
>> Indirectly it is a comparison of implementation and tools
>> benchmarking. Looking at the gpr file, there is no compile switch
>> used, not even an "-o2" switch.
>
> Compiling with -gnatp -O3 would undoubtedly speed it up (suppressing
> checks is justified since execution with checks active shows that no
> checks fail).
>
> Looking casually at the code, the map could be replaced by a constant,
> as Sieve_Size is hard coded to 1,000,000, and the filling of the map is
> included in the timing. The calculation of the square root of 1,000,000
> could be replaced by a constant. The array of Boolean could be
> constrained to 3 .. Sieve_Size. The function that simply returns (others
> => True) could be replaced by the aggregate, though optimization will
> probably do that. Long_Long_Integer could be replaced by a type with
> range 0 .. 2 ** 31 - 1, though I don't know if that would have any
> effect. The first inner loop in the sieve algorithm could be eliminated,
> in which case the initialization of Num could also be removed.

Exactly, this is what is wrong with such contests. The solution is
non-scalable giving advantage to low-level languages like C. Scalability
and readability has the price that hobby-sized instances work poorly.

P.S. I would also suggest ensuring the Boolean array not packed. If not
with compiler switches and pragmas then by declaring a custom Boolean
1,2,4,8 bytes long depending on the target architecture. It is not a
fair play, guys!

--
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

On 08/07/2021 09:20, Jeffrey R. Carter wrote:
> On 7/8/21 5:46 AM, Richard Iswara wrote:
>> Indirectly it is a comparison of implementation and tools
>> benchmarking. Looking at the gpr file, there is no compile switch
>> used, not even an "-o2" switch.

I did wonder about that as I haven't got around to looking through it yet.

> Compiling with -gnatp -O3 would undoubtedly speed it up (suppressing
> checks is justified since execution with checks active shows that no
> checks fail).

I got nothing from the output of trying to run just the Ada version.

> Looking casually at the code, the map could be replaced by a constant,
> as Sieve_Size is hard coded to 1,000,000, and the filling of the map is
> included in the timing. The calculation of the square root of 1,000,000
> could be replaced by a constant. The array of Boolean could be
> constrained to 3 .. Sieve_Size. The function that simply returns (others
> => True) could be replaced by the aggregate, though optimization will
> probably do that. Long_Long_Integer could be replaced by a type with
> range 0 .. 2 ** 31 - 1, though I don't know if that would have any

In the video he mentions Pascal's version only being 32 bit and his is 64.

On 7/8/21 10:20 AM, Jeffrey R. Carter wrote:
>
> Compiling with -gnatp -O3 would undoubtedly speed it up (suppressing checks is
> justified since execution with checks active shows that no checks fail).
>
> Looking casually at the code, the map could be replaced by a constant, as
> Sieve_Size is hard coded to 1,000,000, and the filling of the map is included in
> the timing. The calculation of the square root of 1,000,000 could be replaced by
> a constant. The array of Boolean could be constrained to 3 .. Sieve_Size. The
> function that simply returns (others => True) could be replaced by the
> aggregate, though optimization will probably do that. Long_Long_Integer could be
> replaced by a type with range 0 .. 2 ** 31 - 1, though I don't know if that
> would have any effect. The first inner loop in the sieve algorithm could be
> eliminated, in which case the initialization of Num could also be removed.

Compiling the original code with

gnatmake prime_sieve.adb

gives 408 passes in 5 seconds.

Making the changes listed above (I used Interfaces.Integer_32) and compiling with

gnatmake -O3 prime_sieve.adb

(to ensure that no checks fail) gives 2087 passes in 5 seconds, for a factor of 5.1.

Applying that to the reported 67 passes/second for the original on the test
system implies that this version, compiled with checks enabled and optimization,
would give 343 passes/second.

--
Jeff Carter
"My legs are gray, my ears are gnarled, my eyes are old and bent."
Monty Python's Life of Brian
81

On 08/07/2021 11:42, Jeffrey R. Carter wrote:

Here's the playlist
https://youtube.com/playlist?list=PLF2KJ6Gy3cZ5Er-1eF9fN1Hgw_xkoD9V1 the
second video is where he sets up Python, C# and C++.

> Compiling the original code with
>
> gnatmake prime_sieve.adb
>
> gives 408 passes in 5 seconds.
>
> Making the changes listed above (I used Interfaces.Integer_32) and
> compiling with
>
> gnatmake -O3 prime_sieve.adb
>
> (to ensure that no checks fail) gives 2087 passes in 5 seconds, for a
> factor of 5.1.

He shows the C++ jumping from 4645 (https://youtu.be/D3h62rgewZM?t=1246)
to 7,436 (https://youtu.be/D3h62rgewZM?t=1306) passes going from 32 to
64 bit.

He also uses clang's -Ofast option to compile for speed over size.

On 7/8/21 12:51 PM, Luke A. Guest wrote:
>
> On 08/07/2021 11:42, Jeffrey R. Carter wrote:
>
> Here's the playlist
> https://youtube.com/playlist?list=PLF2KJ6Gy3cZ5Er-1eF9fN1Hgw_xkoD9V1 the second
> video is where he sets up Python, C# and C++.
>
>> Compiling the original code with
>>
>> gnatmake prime_sieve.adb
>>
>> gives 408 passes in 5 seconds.
>>
>> Making the changes listed above (I used Interfaces.Integer_32) and compiling with
>>
>> gnatmake -O3 prime_sieve.adb
>>
>> (to ensure that no checks fail) gives 2087 passes in 5 seconds, for a factor
>> of 5.1.
>
> He shows the C++ jumping from 4645 (https://youtu.be/D3h62rgewZM?t=1246) to
> 7,436 (https://youtu.be/D3h62rgewZM?t=1306) passes going from 32 to 64 bit.
>
> He also uses clang's -Ofast option to compile for speed over size.

Going back to 64-bit integers gives 1999; with -gnatp, 2098

--
Jeff Carter
"My legs are gray, my ears are gnarled, my eyes are old and bent."
Monty Python's Life of Brian
81

On 08/07/2021 12:12, Jeffrey R. Carter wrote:

>> He also uses clang's -Ofast option to compile for speed over size.
>
> Going back to 64-bit integers gives 1999; with -gnatp, 2098
>

I've uploaded my version here
https://github.com/Lucretia/Primes/tree/add-optimised-ada/PrimeAda/solution_2

It's as straight a conversion from the C++ to Ada. I intend to keep
optimising it.

On 08/07/2021 18:37, Luke A. Guest wrote:
> On 08/07/2021 12:12, Jeffrey R. Carter wrote:
>
>>> He also uses clang's -Ofast option to compile for speed over size.
>>
>> Going back to 64-bit integers gives 1999; with -gnatp, 2098
>>
>
> I've uploaded my version here
> https://github.com/Lucretia/Primes/tree/add-optimised-ada/PrimeAda/solution_2
>
>
> It's as straight a conversion from the C++ to Ada. I intend to keep
> optimising it.

As a quick test, I removed the Pack attribute from the Bits array and
got the following speed:

debug0:
Passes: 1108, Time: 5.003198, Avg: 0.004515521, Limit: 1000000,
Count1: 78498, Count2: 78498, Valid: TRUE
Lucretia;1108; 5.003198;algorithm=base,faithful=yes,bits=8

optimised:
Passes: 3286, Time: 5.000592, Avg: 0.001521786, Limit: 1000000,
Count1: 78498, Count2: 78498, Valid: TRUE
Lucretia;3286; 5.000592;algorithm=base,faithful=yes,bits=8

On 08/07/2021 18:43, Luke A. Guest wrote:
> debug0:
> Passes: 1108, Time:  5.003198, Avg:  0.004515521, Limit: 1000000,
> Count1: 78498, Count2: 78498, Valid: TRUE
> Lucretia;1108; 5.003198;algorithm=base,faithful=yes,bits=8
>
> optimised:
> Passes: 3286, Time:  5.000592, Avg:  0.001521786, Limit: 1000000,
> Count1: 78498, Count2: 78498, Valid: TRUE
> Lucretia;3286; 5.000592;algorithm=base,faithful=yes,bits=8

I've updated again, moving the main function to the generic, strange
results.

This also now used packed and unpacked boolean arrays.

I'd be interested to see what numbers your machines get, mine's a tad
ancient now.

On 08/07/2021 18:37, Luke A. Guest wrote:
> On 08/07/2021 12:12, Jeffrey R. Carter wrote:
>
>>> He also uses clang's -Ofast option to compile for speed over size.
>>
>> Going back to 64-bit integers gives 1999; with -gnatp, 2098
>>
>
> I've uploaded my version here
> https://github.com/Lucretia/Primes/tree/add-optimised-ada/PrimeAda/solution_2
>
>
> It's as straight a conversion from the C++ to Ada. I intend to keep
> optimising it.

On Friday, July 9, 2021 at 2:16:54 AM UTC+7, Luke A. Guest wrote:
> On 08/07/2021 18:37, Luke A. Guest wrote:
> > On 08/07/2021 12:12, Jeffrey R. Carter wrote:
> >
> >>> He also uses clang's -Ofast option to compile for speed over size.
> >>
> >> Going back to 64-bit integers gives 1999; with -gnatp, 2098
> >>
> >
> > I've uploaded my version here
> > https://github.com/Lucretia/Primes/tree/add-optimised-ada/PrimeAda/solution_2
> >
> >
> > It's as straight a conversion from the C++ to Ada. I intend to keep
> > optimising it.
Thank you. Well done.

"Luke A. Guest" <laguest@archeia.com> writes:
> It's as straight a conversion from the C++ to Ada. I intend to keep
> optimising it.

I'd be interested in seeing a straight conversion of Pascal to Ada, if
the existing Ada code differs significantly from the existing Pascal
code in a way that affects the speed and isn't a straightforward
conversion.

On Friday, July 9, 2021 at 10:10:37 AM UTC+2, Paul Rubin wrote:
> "Luke A. Guest" <> writes:
> > It's as straight a conversion from the C++ to Ada. I intend to keep
> > optimising it.
> I'd be interested in seeing a straight conversion of Pascal to Ada, if
> the existing Ada code differs significantly from the existing Pascal
> code in a way that affects the speed and isn't a straightforward
> conversion.

One significant difference between the original Ada version and the Pascal and C++ versions, is
that Ada is missing a Num := Factor before the first inner loop.
(Luke fixed that in his version, though)

On Thursday, July 8, 2021 at 7:38:19 PM UTC+2, Luke A. Guest wrote:
> On 08/07/2021 12:12, Jeffrey R. Carter wrote:
>
> >> He also uses clang's -Ofast option to compile for speed over size.
> >
> > Going back to 64-bit integers gives 1999; with -gnatp, 2098
> >
> I've uploaded my version here
> https://github.com/Lucretia/Primes/tree/add-optimised-ada/PrimeAda/solution_2
>
> It's as straight a conversion from the C++ to Ada. I intend to keep
> optimising it.

On my computer, at least, GNAT is not happy about incrementing Number by 2
in the inner loop. I get a bit better performance by modifying the check to

if Number mod 2 /= 0 and then Sieve.Bits(Index_Type(Number)) then

and then incrementing Number by 1.

Or even rewriting to a for-loop

Is_Prime : for Foo in Index_Type (Factor)..Sieve.Size loop
if Foo mod 2 /= 0 and then Sieve.Bits (Foo) then
Factor := Integer(Foo);
exit Is_Prime;
end if;
end loop Is_Prime;

On 7/9/21 10:33 AM, Egil H H wrote:
>
> On my computer, at least, GNAT is not happy about incrementing Number by 2
> in the inner loop. I get a bit better performance by modifying the check to
>
> if Number mod 2 /= 0 and then Sieve.Bits(Index_Type(Number)) then
>
> and then incrementing Number by 1.

Since both operands are positive, mod and rem give the same results, and rem is
usually a bit faster. It's normally not an issue, but in this case it's done
billions of times, so it might make a difference.

--
Jeff Carter
"Oh Lord, bless this thy hand grenade, that with it thou
mayst blow thine enemies to tiny bits, in thy mercy."
Monty Python and the Holy Grail
24

On 7/9/21 11:16 AM, Jeffrey R. Carter wrote:
> On 7/9/21 10:33 AM, Egil H H wrote:
>>
>> On my computer, at least, GNAT is not happy about incrementing Number by 2
>> in the inner loop. I get a bit better performance by modifying the check to
>>
>>        if Number mod 2 /= 0 and then Sieve.Bits(Index_Type(Number)) then
>>
>> and then incrementing Number by 1.
>
> Since both operands are positive, mod and rem give the same results, and rem is
> usually a bit faster. It's normally not an issue, but in this case it's done
> billions of times, so it might make a difference.

Note also that short-circuit forms (and then) require disabling processor-level
optimizations and may have a negative effect on execution time when used
unnecessarily.

--
Jeff Carter
"Oh Lord, bless this thy hand grenade, that with it thou
mayst blow thine enemies to tiny bits, in thy mercy."
Monty Python and the Holy Grail
24

On Wed, 7 Jul 2021 07:21:55 -0700 (PDT), Richard Iswara
<haujekchifan@gmail.com> declaimed the following:

>I haven't seen this posted before so apologies if redundant.
>A couple days ago this person posted on YouTube this clip: https://www.youtube.com/watch?v=pv4Yq35Chx0.
>In the video it was run against Pascal and Ada lost by being 50% slower than Pascal on Prime Sieving. Also shown as 2 orders of magnitude slower than the fastest implementation of that day. See on video at 20:45.
>This is the base implementation link: https://github.com/PlummersSoftwareLLC/Primes/blob/drag-race/PrimeAda/solution_1/src/main.adb.
>I know it's trivial, and probably click bait on the video person, but this is not a good PR on Ada reputation. The guy said do a better implementation to get a better score. So can Ada implementation do better?

It also showed up on the Free-Pascal group. Though their the concern
was relative to a C/C++ implementation.

The kicker... Said C/C++ implementation declared practically everything
as "constexpr" (or some such), and a Google search indicated that such
items are computed BY THE COMPILER! Not at executable run-time.
Run-time basically was "yup, we found them all".

--
Wulfraed Dennis Lee Bieber AF6VN
wlfraed@ix.netcom.com http://wlfraed.microdiversity.freeddns.org/

On Friday, 9 July 2021 at 10:21:05 UTC+1, Jeffrey R. Carter wrote:
> On 7/9/21 11:16 AM, Jeffrey R. Carter wrote:
> >> if Number mod 2 /= 0 and then Sieve.Bits(Index_Type(Number)) then
> >>
> >> and then incrementing Number by 1.
> >
> > Since both operands are positive, mod and rem give the same results, and rem is
> > usually a bit faster. It's normally not an issue, but in this case it's done
> > billions of times, so it might make a difference.
> Note also that short-circuit forms (and then) require disabling processor-level
> optimizations and may have a negative effect on execution time when used
> unnecessarily.

You don't need those as the algorithm always starts at 3 and increments by 2.

I managed to get just under 4000 passes with a 1 bit array, but not using Ada's packed array. That's actually the slowest method, strangely.