Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c++ > #118058 > unrolled thread
| Started by | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| First post | 2023-12-10 10:46 +0100 |
| Last post | 2024-02-14 15:57 +0100 |
| Articles | 20 on this page of 213 — 14 participants |
Back to article view | Back to comp.lang.c++
Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-10 10:46 +0100
Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2023-12-10 21:48 +0000
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-11 04:15 +0100
Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2023-12-11 17:12 +0000
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-11 18:19 +0100
Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2023-12-13 15:16 +0000
Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2023-12-13 15:25 +0000
Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2023-12-14 15:06 +0000
Re: Sieve of Erastosthenes optimized to the max red floyd <no.spam.here@its.invalid> - 2023-12-14 08:20 -0800
Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2023-12-23 10:30 -0800
Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2023-12-23 21:20 +0000
Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2023-12-24 00:36 -0800
Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2023-12-29 18:03 +0000
Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-01-13 21:31 -0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-20 13:44 +0100
Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2023-12-21 15:30 +0000
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-21 17:07 +0100
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-21 17:13 +0100
Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2023-12-23 10:21 -0800
Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2023-12-23 21:21 +0000
Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2023-12-24 10:49 -0800
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-21 14:23 -0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-22 04:28 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-21 20:02 -0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-22 17:55 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-23 12:52 -0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-24 11:03 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-24 13:24 -0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-26 06:00 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-25 21:39 -0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-26 10:27 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-26 12:24 -0800
Re: Sieve of Erastosthenes optimized to the max Kaz Kylheku <433-929-6894@kylheku.com> - 2023-12-26 23:35 +0000
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-26 15:37 -0800
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-26 21:59 -0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-27 10:23 +0100
Re: Sieve of Erastosthenes optimized to the max Kaz Kylheku <433-929-6894@kylheku.com> - 2023-12-27 20:49 +0000
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-28 12:00 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-28 15:38 -0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-29 04:17 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-28 20:58 -0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-29 10:58 +0100
Re: Sieve of Erastosthenes optimized to the max David Brown <david.brown@hesbynett.no> - 2023-12-29 13:56 +0100
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-29 17:04 +0100
Re: Sieve of Erastosthenes optimized to the max David Brown <david.brown@hesbynett.no> - 2023-12-30 19:27 +0100
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-31 11:22 +0100
Re: Sieve of Erastosthenes optimized to the max scott@slp53.sl.home (Scott Lurndal) - 2023-12-31 18:49 +0000
Re: Sieve of Erastosthenes optimized to the max David Brown <david.brown@hesbynett.no> - 2024-01-01 12:46 +0100
Re: Sieve of Erastosthenes optimized to the max scott@slp53.sl.home (Scott Lurndal) - 2023-12-29 16:01 +0000
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-29 17:06 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-29 13:45 -0800
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-29 14:09 -0800
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-29 14:12 -0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-30 05:42 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-29 20:45 -0800
Re: Sieve of Erastosthenes optimized to the max Kaz Kylheku <433-929-6894@kylheku.com> - 2023-12-30 04:56 +0000
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-30 06:09 +0100
Re: Sieve of Erastosthenes optimized to the max Kaz Kylheku <433-929-6894@kylheku.com> - 2023-12-30 05:51 +0000
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-30 10:15 +0100
Re: Sieve of Erastosthenes optimized to the max Kaz Kylheku <433-929-6894@kylheku.com> - 2023-12-30 20:35 +0000
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-31 06:54 +0100
Re: Sieve of Erastosthenes optimized to the max Kaz Kylheku <433-929-6894@kylheku.com> - 2023-12-31 07:01 +0000
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-31 11:20 +0100
Re: Sieve of Erastosthenes optimized to the max Kaz Kylheku <433-929-6894@kylheku.com> - 2023-12-31 17:30 +0000
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-01-01 06:21 +0100
Re: Sieve of Erastosthenes optimized to the max scott@slp53.sl.home (Scott Lurndal) - 2023-12-31 18:44 +0000
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-01-01 06:22 +0100
Re: Sieve of Erastosthenes optimized to the max Kaz Kylheku <433-929-6894@kylheku.com> - 2024-01-01 08:28 +0000
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-01-01 14:11 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-01-01 15:36 -0800
Re: Sieve of Erastosthenes optimized to the max Kaz Kylheku <433-929-6894@kylheku.com> - 2023-12-30 04:51 +0000
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-30 12:00 -0800
Re: Sieve of Erastosthenes optimized to the max Kaz Kylheku <433-929-6894@kylheku.com> - 2023-12-29 17:29 +0000
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-30 05:45 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-30 11:58 -0800
Re: Sieve of Erastosthenes optimized to the max red floyd <no.spam.here@its.invalid> - 2023-12-30 14:58 -0800
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-31 11:49 -0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-31 06:51 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-31 11:36 -0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-01-01 07:28 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-31 22:53 -0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-01-01 14:11 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-01-01 15:34 -0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-01-02 11:55 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-01-02 10:38 -0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-01-03 06:48 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-01-03 13:32 -0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-01-04 04:37 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-01-05 19:21 -0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-01-06 08:18 +0100
Re: Sieve of Erastosthenes optimized to the max Kaz Kylheku <433-929-6894@kylheku.com> - 2024-01-06 08:31 +0000
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-01-06 10:30 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-01-06 13:15 -0800
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-01-06 13:19 -0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-01-07 10:14 +0100
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-01-07 10:10 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-01-07 12:46 -0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-01-08 06:48 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-01-08 12:18 -0800
Re: Sieve of Erastosthenes optimized to the max red floyd <no.spam.here@its.invalid> - 2024-01-08 17:14 -0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-01-09 07:19 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-01-09 23:33 -0800
Re: Sieve of Erastosthenes optimized to the max Kaz Kylheku <433-929-6894@kylheku.com> - 2024-01-09 02:02 +0000
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-01-09 15:12 +0100
OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) Vir Campestris <vir.campestris@invalid.invalid> - 2024-01-29 21:31 +0000
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-02-16 08:06 -0800
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) Bonita Montero <Bonita.Montero@gmail.com> - 2024-02-16 18:30 +0100
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-02-23 05:51 -0800
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) Bonita Montero <Bonita.Montero@gmail.com> - 2024-02-24 10:45 +0100
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-02-25 00:48 -0800
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) Bonita Montero <Bonita.Montero@gmail.com> - 2024-02-25 15:51 +0100
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-11 10:10 -0700
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) Bonita Montero <Bonita.Montero@gmail.com> - 2024-03-12 10:15 +0100
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) wij <wyniijj5@gmail.com> - 2024-03-14 12:44 +0800
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) Bonita Montero <Bonita.Montero@gmail.com> - 2024-03-14 07:25 +0100
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) wij <wyniijj5@gmail.com> - 2024-03-14 17:20 +0800
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) wij <wyniijj5@gmail.com> - 2024-03-14 17:35 +0800
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) wij <wyniijj5@gmail.com> - 2024-03-14 17:41 +0800
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) Bonita Montero <Bonita.Montero@gmail.com> - 2024-03-14 19:20 +0100
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) wij <wyniijj5@gmail.com> - 2024-03-15 16:30 +0800
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) Bonita Montero <Bonita.Montero@gmail.com> - 2024-03-15 11:21 +0100
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) wij <wyniijj5@gmail.com> - 2024-03-15 19:07 +0800
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) Bonita Montero <Bonita.Montero@gmail.com> - 2024-03-15 12:56 +0100
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) Bonita Montero <Bonita.Montero@gmail.com> - 2024-03-14 19:20 +0100
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-20 08:35 -0700
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) Bonita Montero <Bonita.Montero@gmail.com> - 2024-04-20 18:34 +0200
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) Bonita Montero <Bonita.Montero@gmail.com> - 2024-04-20 18:35 +0200
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-24 12:28 -0700
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) Bonita Montero <Bonita.Montero@gmail.com> - 2024-04-25 06:19 +0200
Re: OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-25 14:14 -0700
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-31 11:39 -0800
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-29 13:52 -0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-27 06:06 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-03-22 19:34 -0700
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-03-23 17:54 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-03-23 14:04 -0700
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-03-24 07:30 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-03-24 12:52 -0700
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-03-24 21:00 +0100
Re: Sieve of Erastosthenes optimized to the max "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-03-24 13:05 -0700
Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-05-16 17:28 +0100
Re: Sieve of Erastosthenes optimized to the max Ben Bacarisse <ben@bsb.me.uk> - 2024-05-16 21:40 +0100
Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-05-21 19:06 -0700
Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-05-30 12:32 +0100
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-05-30 14:17 +0200
Re: Sieve of Erastosthenes optimized to the max Paavo Helde <eesnimi@osa.pri.ee> - 2024-05-30 19:55 +0300
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-05-31 10:17 +0200
Re: Sieve of Erastosthenes optimized to the max Paavo Helde <eesnimi@osa.pri.ee> - 2024-05-31 20:52 +0300
Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-05-30 22:17 -0700
Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-06-01 21:07 +0100
Re: Sieve of Erastosthenes optimized to the max Richard Damon <richard@damon-family.org> - 2024-06-01 20:43 -0400
Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-06-02 03:23 -0700
Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-06-02 19:50 -0700
Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-06-18 20:56 +0100
Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-06-18 17:34 -0700
Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-06-30 21:47 +0100
Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-07-01 23:20 -0700
Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-07-02 21:24 +0100
Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-07-03 11:25 +0100
Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-07-15 06:15 -0700
Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-07-20 07:41 -0700
OT: Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-07-25 12:46 +0100
Re: OT: Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-08-10 07:07 -0700
Re: OT: Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-08-12 15:32 +0100
Re: OT: Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-08-16 07:48 -0700
Re: OT: Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-08-15 17:52 +0100
Re: OT: Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-08-16 08:40 -0700
Re: OT: Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-08-16 19:35 +0200
Re: OT: Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-08-16 19:55 +0200
Re: OT: Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-08-19 21:23 +0100
Re: OT: Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-08-20 17:21 +0200
Re: OT: Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-08-20 17:24 +0200
Re: OT: Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-08-20 17:43 +0200
Re: OT: Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-08-20 17:55 +0100
Re: OT: Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-08-20 18:59 +0200
Re: OT: Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-08-26 12:08 -0700
Re: OT: Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-08-27 06:09 +0200
Re: OT: Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-09-01 21:23 +0100
Re: OT: Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-09-01 20:40 -0700
Re: OT: Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-09-02 07:08 +0200
Re: OT: Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-09-03 17:45 +0100
Re: OT: Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-09-28 03:46 -0700
Re: OT: Re: Sieve of Erastosthenes optimized to the max Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2024-09-28 13:49 -0700
Re: OT: Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-10-02 11:44 +0100
Re: OT: Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-10-02 13:10 +0200
Re: OT: Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-10-07 08:41 -0700
Re: OT: Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-10-20 12:44 +0100
Re: OT: Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-11-04 03:56 -0800
Re: OT: Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-08-19 21:34 +0100
Re: OT: Re: Sieve of Erastosthenes optimized to the max red floyd <no.spam.here@its.invalid> - 2024-08-19 21:08 -0700
Re: OT: Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-08-20 21:14 +0100
Re: OT: Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-08-26 09:35 -0700
Re: OT: Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-08-26 08:31 -0700
Re: OT: Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-08-20 19:20 +0200
Re: OT: Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-08-20 19:36 +0200
Re: OT: Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-08-20 19:39 +0200
Re: OT: Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-08-20 20:13 +0200
Re: OT: Re: Sieve of Erastosthenes optimized to the max scott@slp53.sl.home (Scott Lurndal) - 2024-08-20 20:50 +0000
Re: OT: Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-08-22 17:30 +0100
Re: OT: Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-08-22 18:38 +0200
Re: OT: Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-08-22 21:47 +0100
Re: OT: Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-08-22 21:56 +0100
Re: OT: Re: Sieve of Erastosthenes optimized to the max red floyd <no.spam.here@its.invalid> - 2024-08-22 17:00 -0700
Re: OT: Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-08-26 10:59 -0700
Re: OT: Re: Sieve of Erastosthenes optimized to the max Andrey Tarasevich <andreytarasevich@hotmail.com> - 2024-09-28 15:21 -0700
Re: OT: Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-08-26 12:47 -0700
Re: OT: Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-08-18 19:52 -0700
Re: OT: Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-08-10 17:24 -0700
Re: OT: Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-08-11 00:00 -0700
Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-07-23 07:34 -0700
Re: Sieve of Erastosthenes optimized to the max wij <wyniijj5@gmail.com> - 2024-02-14 00:15 +0800
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-02-13 19:08 +0100
Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-02-14 15:57 +0100
Page 1 of 11 [1] 2 3 … 11 Next page →
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2023-12-10 10:46 +0100 |
| Subject | Sieve of Erastosthenes optimized to the max |
| Message-ID | <ul41d4$2koct$1@raubtier-asyl.eternal-september.org> |
I've parallelized my sieve of Erastosthenes to all cores. The parallel
threads do al the punching of the non-prime multiplex beyond sqrt( max
). I found that the algorithm is limited by the memory bandwith since
the bit-range between sqrt( max ) and max is to large to fit inside
the cache. So I partitioned the each thread to a number of bit-ranges
that fits inside the L2-cache. With that I got a speedup of factor 28
when calculating about the first 210 million primes, i.e. all primes
<= 2 ^ 32.
On my Zen4 16 core PC under Windows with clang-cl 16.0.5 producing the
primes without any file output is only 0.28s. On my Linux-PC, a Zen2 64
core CPU producing the same number of primes is about 0.09s.
The file output is done with my own buffering. With that writing the
mentioned prime number range results in a 2.2GB file which is written
in about two seconds with a PCIe 4.0 SSD.
The first parameter is the highest prime candidate to be generated,
it can be prefixed with 0x for hex values. The second number is the
name of the output file; it can be "" to suppress file output. The
third parameter is the number of punching threads; if it is left the
number of threads defaults to the number of threads reported by the
runtime.
#include <iostream>
#include <cstdlib>
#include <charconv>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <bit>
#include <fstream>
#include <string_view>
#include <thread>
#include <mutex>
#include <condition_variable>
#include <utility>
#include <semaphore>
#include <atomic>
#include <new>
#include <span>
#if defined(_MSC_VER)
#include <intrin.h>
#elif defined(__GNUC__) || defined(__clang__)
#include <cpuid.h>
#endif
#if defined(_MSC_VER)
#pragma warning(disable: 26495)
#endif
using namespace std;
#if defined(__cpp_lib_hardware_interference_size)
constexpr ptrdiff_t CL_SIZE = hardware_destructive_interference_size;
#else
constexpr ptrdiff_t CL_SIZE = 64;
#endif
size_t getL2Size();
int main( int argc, char **argv )
{
if( argc < 2 )
return EXIT_FAILURE;
auto parse = []( char const *str, bool hex, auto &value )
{
from_chars_result fcr = from_chars( str, str + strlen( str ), value,
!hex ? 10 : 16 );
return fcr.ec == errc() && !*fcr.ptr;
};
char const *sizeStr = argv[1];
bool hex = sizeStr[0] == '0' && (sizeStr[1] == 'x' || sizeStr[1] == 'X');
sizeStr += 2 * hex;
size_t end;
if( !parse( sizeStr, hex, end ) )
return EXIT_FAILURE;
if( (ptrdiff_t)end++ < 0 )
throw bad_alloc();
unsigned hc;
if( argc < 4 || !parse( argv[3], false, hc ) )
hc = jthread::hardware_concurrency();
if( !hc )
return EXIT_FAILURE;
using word_t = size_t;
constexpr size_t
BITS = sizeof(word_t) * 8,
CL_BITS = CL_SIZE * 8;
union alignas(CL_SIZE) ndi_words_cl { word_t words[CL_SIZE /
sizeof(word_t)]; ndi_words_cl() {} };
size_t nCls = (end + CL_BITS - 1) / CL_BITS;
vector<ndi_words_cl> sieveCachelines( (end + CL_BITS - 1) / CL_BITS );
size_t nWords = (end + BITS - 1) / BITS;
span<word_t> sieve( &sieveCachelines[0].words[0], nWords );
auto fill = sieve.begin();
*fill++ = (word_t)0xAAAAAAAAAAAAAAACu;
if( fill != sieve.end() )
for_each( fill, sieve.end(), []( word_t &w ) { w =
(word_t)0xAAAAAAAAAAAAAAAAu; } );
size_t sqrt = (ptrdiff_t)ceil( ::sqrt( (ptrdiff_t)end ) );
auto punch = [&]( auto, size_t start, size_t end, size_t prime )
{
if( start >= end )
return;
size_t multiple = start;
if( prime >= BITS ) [[likely]]
do
sieve[multiple / BITS] &= rotl( (word_t)-2, multiple % BITS );
while( (multiple += prime) < end );
else
{
auto pSieve = sieve.begin() + multiple / BITS;
do
{
word_t
word = *pSieve,
mask = rotl( (word_t)-2, multiple % BITS ),
oldMask;
do
word &= mask,
oldMask = mask,
mask = rotl( mask, prime % BITS ),
multiple += prime;
while( mask < oldMask );
*pSieve++ = word;
} while( multiple < end );
}
};
for( size_t prime = 3; prime < sqrt; ++prime )
{
for( auto pSieve = sieve.begin() + prime / BITS; ; )
{
if( word_t w = *pSieve >> prime % BITS; w ) [[likely]]
{
prime += countr_zero( w );
break;
}
prime = prime + BITS & -(ptrdiff_t)BITS;
if( prime >= sqrt )
break;
}
if( prime >= sqrt ) [[unlikely]]
break;
punch( false_type(), prime * prime, sqrt, prime );
}
auto scan = [&]( size_t start, size_t end, auto fn )
{
for( size_t prime = start; prime < end; )
{
word_t word = sieve[prime / BITS] >> prime % BITS;
bool hasBits = word;
for( unsigned gap; word; word >>= gap, word >>= 1 )
{
gap = countr_zero( word );
if( (prime += gap) >= end ) [[unlikely]]
return;
fn( prime );
if( ++prime >= end ) [[unlikely]]
return;
}
prime = (prime + BITS - hasBits) & -(ptrdiff_t)BITS;
}
};
size_t bitsPerPartition = (end - sqrt) / hc;
using range_t = pair<size_t, size_t>;
vector<pair<size_t, size_t>> ranges;
ranges.reserve( hc );
for( size_t t = hc, rEnd = end, rStart; t--; rEnd = rStart )
{
rStart = sqrt + t * bitsPerPartition;
size_t rClStart = rStart & -(CL_SIZE * 8);
rStart = rClStart >= sqrt ? rClStart : sqrt;
if( rStart >= rEnd )
continue;
ranges.emplace_back( rStart, rEnd );
}
vector<jthread> threads;
threads.reserve( ranges.size() - 1 );
static auto dbl = []( ptrdiff_t x ) { return (double)x; };
double maxPartitionBits = dbl( getL2Size() ) * 8 / 3;
for( range_t const &range : ranges )
{
auto rangePuncher = [&]( size_t rStart, size_t rEnd )
{
double nBits = dbl( rEnd - rStart );
ptrdiff_t nPartitions = (ptrdiff_t)ceil( nBits / maxPartitionBits );
double bitsPerPartition = nBits / dbl( nPartitions );
for( ptrdiff_t p = nPartitions, pEnd = rEnd, pStart; p--; pEnd = pStart )
{
pStart = rStart + (ptrdiff_t)((double)p * bitsPerPartition);
pStart &= -(CL_SIZE * 8);
scan( 3, sqrt,
[&]( size_t prime )
{
punch( true_type(), (pStart + prime - 1) / prime * prime, pEnd,
prime );
} );
}
};
if( &range != &ranges.back() )
threads.emplace_back( rangePuncher, range.first, range.second );
else
rangePuncher( range.first, range.second );
}
threads.resize( 0 );
if( argc >= 3 && !*argv[2] )
return EXIT_SUCCESS;
ofstream ofs;
ofs.exceptions( ofstream::failbit | ofstream::badbit );
ofs.open( argc >= 3 ? argv[2] : "primes.txt", ofstream::binary |
ofstream::trunc );
constexpr size_t
BUF_SIZE = 0x100000,
AHEAD = 32;
union ndi_char { char c; ndi_char() {} };
vector<ndi_char> printBuf( BUF_SIZE + AHEAD - 1 );
auto
bufBegin = printBuf.begin(),
bufEnd = bufBegin,
bufFlush = bufBegin + BUF_SIZE;
auto print = [&]() { ofs << string_view( &bufBegin->c, &to_address(
bufEnd )->c ); };
scan( 2, end,
[&]( size_t prime )
{
auto [ptr, ec] = to_chars( &bufEnd->c, &bufEnd[AHEAD - 1].c, prime );
if( ec != errc() ) [[unlikely]]
throw system_error( (int)ec, generic_category(), "converson failed" );
bufEnd = ptr - &bufBegin->c + bufBegin; // pointer to iterator - NOP
bufEnd++->c = '\n';
if( bufEnd >= bufFlush ) [[unlikely]]
print(), bufEnd = bufBegin;
} );
print();
}
size_t getL2Size()
{
int regs[4];
auto cpuId = [&]( unsigned code )
{
#if defined(_MSC_VER)
__cpuid( regs, code );
#elif defined(__GNUC__) || defined(__clang__)
__cpuid(code, regs[0], regs[1], regs[2], regs[3]);
#endif
return regs[0];
};
if( (unsigned)cpuId( 0x80000000u ) < 0x80000006u )
return 512ull * 1024;
cpuId( 0x80000006u );
return ((unsigned)regs[2] >> 16) * 1024;
}
[toc] | [next] | [standalone]
| From | Vir Campestris <vir.campestris@invalid.invalid> |
|---|---|
| Date | 2023-12-10 21:48 +0000 |
| Message-ID | <ul5bn0$2qsht$2@dont-email.me> |
| In reply to | #118058 |
On 10/12/2023 09:46, Bonita Montero wrote: > I've parallelized my sieve of Erastosthenes to all cores. The parallel > threads do al the punching of the non-prime multiplex beyond sqrt( max > ). I found that the algorithm is limited by the memory bandwith since > the bit-range between sqrt( max ) and max is to large to fit inside > the cache. So I partitioned the each thread to a number of bit-ranges > that fits inside the L2-cache. With that I got a speedup of factor 28 > when calculating about the first 210 million primes, i.e. all primes > <= 2 ^ 32. > On my Zen4 16 core PC under Windows with clang-cl 16.0.5 producing the > primes without any file output is only 0.28s. On my Linux-PC, a Zen2 64 > core CPU producing the same number of primes is about 0.09s. > The file output is done with my own buffering. With that writing the > mentioned prime number range results in a 2.2GB file which is written > in about two seconds with a PCIe 4.0 SSD. > The first parameter is the highest prime candidate to be generated, > it can be prefixed with 0x for hex values. The second number is the > name of the output file; it can be "" to suppress file output. The > third parameter is the number of punching threads; if it is left the > number of threads defaults to the number of threads reported by the > runtime. > <snip code> Just so happens I've been thinking about this. I find your code impenetrable - there are no comments at all. But two things occurred to me quite quickly: - You don't need to store the odd numbers - You only need a bitmask to save the sieve. I think you're doing the latter, though it's not obvious. I think you're storing bits in an array of size_t, and that will be what 0xAAAAAAAAAAAAAAACu and 0xAAAAAAAAAAAAAAAAu are about. However if I am reading that right you've assumed that unsigned is the same size as size_t, and that the size is 64 bits. Andy
[toc] | [prev] | [next] | [standalone]
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2023-12-11 04:15 +0100 |
| Message-ID | <ul5ut3$31a17$1@raubtier-asyl.eternal-september.org> |
| In reply to | #118059 |
Am 10.12.2023 um 22:48 schrieb Vir Campestris: > - You don't need to store the odd numbers All primes except 2 are odd. > - You only need a bitmask to save the sieve. I'm using the "scan"-lambda which does serarch through the sieve as fast as possible with countr_zero, which maps to a single CPU -instruction on modern processors. > ... reading that right you've assumed that unsigned is the same > size as size_t, and that the size is 64 bits. I've got a type word_t that is a size_t, but it can also be a uint8_t to test what's the performance difference.
[toc] | [prev] | [next] | [standalone]
| From | Vir Campestris <vir.campestris@invalid.invalid> |
|---|---|
| Date | 2023-12-11 17:12 +0000 |
| Message-ID | <ul7ft1$3853g$1@dont-email.me> |
| In reply to | #118060 |
On 11/12/2023 03:15, Bonita Montero wrote: > Am 10.12.2023 um 22:48 schrieb Vir Campestris: > >> - You don't need to store the odd numbers > > All primes except 2 are odd. > I had a really bad night, and I was half asleep yesterday. Because all primes except 2 are odd you don't need to store the _even_ numbers, which is what I meant to say. Or else you only need to store the odd ones. >> - You only need a bitmask to save the sieve. > > I'm using the "scan"-lambda which does serarch through the sieve > as fast as possible with countr_zero, which maps to a single CPU > -instruction on modern processors. > >> ... reading that right you've assumed that unsigned is the same >> size as size_t, and that the size is 64 bits. > > I've got a type word_t that is a size_t, but it can also > be a uint8_t to test what's the performance difference. > Your constants are 64 bit hexadecimal numbers (from counting the digits) and are unsigned (the u suffix) but there's no guarantee that size_t will be the same size as unsigned, nor that it will be 64 bit. Andy
[toc] | [prev] | [next] | [standalone]
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2023-12-11 18:19 +0100 |
| Message-ID | <ul7gal$3885r$1@raubtier-asyl.eternal-september.org> |
| In reply to | #118061 |
Am 11.12.2023 um 18:12 schrieb Vir Campestris: > Because all primes except 2 are odd you don't need to store the _even_ > numbers, which is what I meant to say. Or else you only need to store > the odd ones. I'll try that the next days; but I don't expect a significant change. > Your constants are 64 bit hexadecimal numbers (from counting the digits) > and are unsigned (the u suffix) but there's no guarantee that size_t > will be the same size as unsigned, nor that it will be 64 bit. The constants are wide enough for 64 bit size_t-s but it won't make a functional difference if you define word_t as a uint8_t. With an uint8_t word_t the code runs about 1/6-th slower; that's less than I expected.
[toc] | [prev] | [next] | [standalone]
| From | Vir Campestris <vir.campestris@invalid.invalid> |
|---|---|
| Date | 2023-12-13 15:16 +0000 |
| Message-ID | <ulchs1$t3ph$1@dont-email.me> |
| In reply to | #118062 |
On 11/12/2023 17:19, Bonita Montero wrote:
> Am 11.12.2023 um 18:12 schrieb Vir Campestris:
>
>> Because all primes except 2 are odd you don't need to store the _even_
>> numbers, which is what I meant to say. Or else you only need to store
>> the odd ones.
>
> I'll try that the next days; but I don't expect a significant change.
>
Well, I went away and tried it. I didn't write anything nearly as
sophisticated as yours - I didn't worry about threads and caching. The
code follows. You'll have to unwrap it in a few places.
It occurred to me I could go further - not just optimise it out to store
odd numbers only, but also miss out the ones divisible by 3, or other
higher primes. The results were:
- Storing all numbers: 9.494 seconds to run the sieve
- Storing odd numbers only: 4.455. That's over twice as fast.
- Excluding also the ones divisible by 3: 3.468. That's an improvement,
but not as much as I expected. Perhaps it's got coo complicated. I don't
have a high powered PC.
>> Your constants are 64 bit hexadecimal numbers (from counting the
>> digits) and are unsigned (the u suffix) but there's no guarantee that
>> size_t will be the same size as unsigned, nor that it will be 64 bit.
>
> The constants are wide enough for 64 bit size_t-s but it won't make
> a functional difference if you define word_t as a uint8_t. With an
> uint8_t word_t the code runs about 1/6-th slower; that's less than
> I expected.
>
Most likely what you are seeing there is that you've gone from being
memory bound to being compute bound. The CPU cache will make sure the
main memory accesses are 128 bits (or whatever your bus width is)
Andy
--
#include <cassert>
#include <chrono>
#include <cmath>
#include <iostream>
#include <thread>
#include <vector>
size_t PrimeCount = 1e8;
// this is a convenience class for timing.
class stopwatch {
std::chrono::time_point<std::chrono::steady_clock> mBegin, mEnd;
public:
stopwatch() {}
// record the start of an interval
void start()
{
mBegin = std::chrono::steady_clock::now();
}
// record the end of an interval
void stop()
{
mEnd = std::chrono::steady_clock::now();
}
// report the difference between the last start and stop
double delta() const
{
return
std::chrono::duration_cast<std::chrono::milliseconds>(mEnd -
mBegin).count() / 1000.0;
}
};
// the bitmask will be stores in a class that looks like this
class Primes
{
public:
Primes(size_t size) {};
virtual ~Primes() {};
virtual void unprime(size_t value) = 0; // marks a number
as not prime
virtual bool get(size_t value) const = 0; // gets how a
number is marked
virtual size_t size() const = 0; // Size of the store
};
// Basic store. Stores all the primes in a vector<bool>
class PrimesVB: public Primes
{
std::vector<bool> mStore;
public:
PrimesVB(size_t size) : Primes(size), mStore(size, true) {};
virtual void unprime(size_t value) override
{
mStore[value] = false;
}
virtual bool get(size_t value) const override
{
return mStore[value];
}
virtual size_t size() const override
{
return mStore.size();
}
};
class Primes2: public PrimesVB
{
size_t mSize;
public:
Primes2(size_t size) : PrimesVB((size + 1) / 2), mSize(size) {};
virtual void unprime(size_t value) override
{
if (value & 1)
PrimesVB::unprime(value / 2);
}
virtual bool get(size_t value) const override
{
if (value <= 2) return true;
return (value & 1) && PrimesVB::get(value / 2);
}
virtual size_t size() const override
{
return mSize;
}
};
class Primes23: public PrimesVB
{
// Size of the map. This is a lot bigger than the size of the
bitmap.
size_t mSize;
// each "page" contains 2 "lines". A line is a prime we are
storing.
// this map is where we store each number, depending on its
value modulo 6.
// -1 is known not to be prime, and isn't stored.
// we store 7, 13, 18 in "line" 0; 11, 17, 23 in "line" 1.
// the others are either divisible by 2 or 3, and don't need to
be stored.
static constexpr int mPosMap[6] = {-1, 0, -1, -1, -1, 1};
public:
Primes23(size_t size) : PrimesVB((size + 2) / 3), mSize(size) {};
virtual void unprime(size_t value) override
{
if (value <= 3) return;
auto page = value / 6;
auto line = mPosMap[value % 6];
if (line >= 0)
{
PrimesVB::unprime(page * 2 + line);
}
}
virtual bool get(size_t value) const override
{
if (value <= 3) return true;
auto page = value / 6; // 5=0 7=1 11=1 13=2
auto line = mPosMap[value % 6]; // 5=2 7=0 11=2 13=0
if (line >= 0)
{
return PrimesVB::get(page * 2 + line);
}
else
{
return false;
}
}
virtual size_t size() const override
{
return mSize;
}
};
// Simple sieve of Eratosthenes function
void sieve(Primes& store)
{
const size_t storesize = store.size();
const size_t maxfilter = std::ceil(std::sqrt(storesize));
size_t prime = 2;
while (prime < maxfilter)
{
// Unmark all the multiples
for (size_t inval = prime*2; inval < storesize; inval+=
prime)
store.unprime(inval);
// Find the next prime to filter with
while (!store.get(++prime) && prime < maxfilter) {};
}
}
// Benchmark function. Returns the constructed collection for validation.
template <typename storetype> storetype test(const char* classname)
{
stopwatch s;
s.start();
storetype store(PrimeCount);
s.stop();
std::cout << classname << " construct " << s.delta() << "
seconds." << std::endl;
s.start();
sieve(store);
s.stop();
std::cout << classname << " sieve " << s.delta() << " seconds."
<< std::endl;
return store;
}
int main()
{
auto vb = test<PrimesVB>("vector<bool>");
auto p2 = test<Primes2>("Storing odds only");
auto p23 = test<Primes23>("Not storing 2s and 3s");
// double check they all match.
for (auto p = 1; p < PrimeCount; ++p)
{
assert(vb.get(p) == p2.get(p));
assert(vb.get(p) == p23.get(p));
}
return 0;
}
[toc] | [prev] | [next] | [standalone]
| From | Vir Campestris <vir.campestris@invalid.invalid> |
|---|---|
| Date | 2023-12-13 15:25 +0000 |
| Message-ID | <ulcidm$t3ph$2@dont-email.me> |
| In reply to | #118063 |
On 13/12/2023 15:16, Vir Campestris wrote: > Well, I went away and tried it. I didn't write anything nearly as > sophisticated as yours - I didn't worry about threads and caching. The > code follows. You'll have to unwrap it in a few places. > > It occurred to me I could go further - not just optimise it out to store > odd numbers only, but also miss out the ones divisible by 3, or other > higher primes. The results were: > - Storing all numbers: 9.494 seconds to run the sieve > - Storing odd numbers only: 4.455. That's over twice as fast. > - Excluding also the ones divisible by 3: 3.468. That's an improvement, > but not as much as I expected. Perhaps it's got coo complicated. I don't > have a high powered PC. And no sooner had I posted that than I realised I'd got the optimisation settings wrong. With -Ofast fed to g++ the version that doesn't store multiples of 3 is _slower_ than the odds only one! Andy
[toc] | [prev] | [next] | [standalone]
| From | Vir Campestris <vir.campestris@invalid.invalid> |
|---|---|
| Date | 2023-12-14 15:06 +0000 |
| Message-ID | <ulf5l6$1e43l$1@dont-email.me> |
| In reply to | #118064 |
I tried a few more collections. The slowest on my system is vector<bool> 12.165s for 1e9 primes. Having a manual bitmask, and storing in uint64_t is a lot faster - almost twice as fast (6.659). A uint32_t is a little faster than that (6.306). Optimising it to store odds only more than doubles the speed of vector<bool> to 5.107 seconds. That has less effect with uint64_t, taking it to 4.946 - which is the best time I have. Oddly storing odds only with uint32_t is not as fast as odds only with uint64_t, although it is still faster than storing all the values (5.302). I've optimised it to do less recursion, which has helped, but it still isn't worth not storing the multiples of 3. I'll guess that's because that code required a divide and mod by 6, whereas optimising out the evens only requires shifts and masks. Andy
[toc] | [prev] | [next] | [standalone]
| From | red floyd <no.spam.here@its.invalid> |
|---|---|
| Date | 2023-12-14 08:20 -0800 |
| Message-ID | <ulfa02$1er97$1@redfloyd.dont-email.me> |
| In reply to | #118063 |
On 12/13/2023 7:16 AM, Vir Campestris wrote: > On 11/12/2023 17:19, Bonita Montero wrote: >> Am 11.12.2023 um 18:12 schrieb Vir Campestris: >> >>> Because all primes except 2 are odd you don't need to store the >>> _even_ numbers, which is what I meant to say. Or else you only need >>> to store the odd ones. >> >> I'll try that the next days; but I don't expect a significant change. >> > Well, I went away and tried it. I didn't write anything nearly as > sophisticated as yours - I didn't worry about threads and caching. The > code follows. You'll have to unwrap it in a few places. > > It occurred to me I could go further - not just optimise it out to store > odd numbers only, but also miss out the ones divisible by 3, or other > higher primes. The results were: > - Storing all numbers: 9.494 seconds to run the sieve > - Storing odd numbers only: 4.455. That's over twice as fast. > - Excluding also the ones divisible by 3: 3.468. That's an improvement, > but not as much as I expected. Perhaps it's got coo complicated. I don't > have a high powered PC. Another way to attempt to optimize is that except for 2 and 3, all primes are of the form 6n+1 or 6n-1.
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2023-12-23 10:30 -0800 |
| Message-ID | <86edfcvkjm.fsf@linuxsc.com> |
| In reply to | #118066 |
red floyd <no.spam.here@its.invalid> writes:
> On 12/13/2023 7:16 AM, Vir Campestris wrote:
>
>> On 11/12/2023 17:19, Bonita Montero wrote:
>>
>>> Am 11.12.2023 um 18:12 schrieb Vir Campestris:
>>>
>>>> Because all primes except 2 are odd you don't need to store the
>>>> _even_ numbers, which is what I meant to say. Or else you only
>>>> need to store the odd ones.
>>>
>>> I'll try that the next days; but I don't expect a significant change.
>>
>> Well, I went away and tried it. I didn't write anything nearly as
>> sophisticated as yours - I didn't worry about threads and
>> caching. The code follows. You'll have to unwrap it in a few places.
>>
>> It occurred to me I could go further - not just optimise it out to
>> store odd numbers only, but also miss out the ones divisible by 3,
>> or other higher primes. The results were:
>> - Storing all numbers: 9.494 seconds to run the sieve
>> - Storing odd numbers only: 4.455. That's over twice as fast.
>> - Excluding also the ones divisible by 3: 3.468. That's an
>> improvement, but not as much as I expected. Perhaps it's got coo
>> complicated. I don't have a high powered PC.
>
> Another way to attempt to optimize is that except for 2 and 3, all
> primes are of the form 6n+1 or 6n-1.
A more compact form is to consider numbers mod 30, in which case
numbers that are 0 mod {2, 3, or 5} can be ignored. Conveniently
there are just 8 such values - 1, 7, 11, 13, 17, 19, 23, and 29 -
so each block of 30 can be represented in one 8-bit byte. Doing
that gives a 25% reduction in space compared to a 6n+/-1 scheme.
[toc] | [prev] | [next] | [standalone]
| From | Vir Campestris <vir.campestris@invalid.invalid> |
|---|---|
| Date | 2023-12-23 21:20 +0000 |
| Message-ID | <um7iva$27ikh$1@dont-email.me> |
| In reply to | #118119 |
On 23/12/2023 18:30, Tim Rentsch wrote:
> A more compact form is to consider numbers mod 30, in which case
> numbers that are 0 mod {2, 3, or 5} can be ignored. Conveniently
> there are just 8 such values - 1, 7, 11, 13, 17, 19, 23, and 29 -
> so each block of 30 can be represented in one 8-bit byte. Doing
> that gives a 25% reduction in space compared to a 6n+/-1 scheme.
I found that on my system the modulo operation was so slow this wasn't
worth doing.
Andy
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2023-12-24 00:36 -0800 |
| Message-ID | <86a5q0uhd1.fsf@linuxsc.com> |
| In reply to | #118121 |
Vir Campestris <vir.campestris@invalid.invalid> writes:
> On 23/12/2023 18:30, Tim Rentsch wrote:
>
>> A more compact form is to consider numbers mod 30, in which case
>> numbers that are 0 mod {2, 3, or 5} can be ignored. Conveniently
>> there are just 8 such values - 1, 7, 11, 13, 17, 19, 23, and 29 -
>> so each block of 30 can be represented in one 8-bit byte. Doing
>> that gives a 25% reduction in space compared to a 6n+/-1 scheme.
>
> I found that on my system the modulo operation was so slow this wasn't
> worth doing.
Depending on how the code is written, no modulo operations need
to be done, because they will be optimized away and done at
compile time. If we look at multiplying two numbers represented
by bits in bytes i and j, the two numbers are
i*30 + a
j*30 + b
for some a and b in { 1, 7, 11, 13 17, 19, 23, 29 }.
The values we're interested in are the index of the product and
the residue of the product, namely
(i*30+a) * (j*30+b) / 30 (for the index)
(i*30+a) * (j*30+b) % 30 (for the residue)
Any term with a *30 in the numerator doesn't contribute to
the residue, and also can be combined with the by-30 divide
for computing the index. Thus these expressions can be
rewritten as
i*30*j + i*b + j*a + (a*b/30) (for the index)
a*b%30 (for the residue)
When a and b have values that are known at compile time,
neither the divide nor the remainder result in run-time
operations being done; all of that heavy lifting is
optimized away and done at compile time. Of course there
are some multiplies, but they are cheaper than divides, and
also can be done in parallel. (The multiplication a*b also
can be done at compile time.)
The residue needs to be turned into a bit mask to do the
logical operation on the byte of bits, but here again that
computation can be optimized away and done at compile time.
Does that all make sense?
[toc] | [prev] | [next] | [standalone]
| From | Vir Campestris <vir.campestris@invalid.invalid> |
|---|---|
| Date | 2023-12-29 18:03 +0000 |
| Message-ID | <umn1ma$svun$7@dont-email.me> |
| In reply to | #118124 |
On 24/12/2023 08:36, Tim Rentsch wrote:
> Depending on how the code is written, no modulo operations need
> to be done, because they will be optimized away and done at
> compile time. If we look at multiplying two numbers represented
> by bits in bytes i and j, the two numbers are
>
> i*30 + a
> j*30 + b
>
> for some a and b in { 1, 7, 11, 13 17, 19, 23, 29 }.
>
> The values we're interested in are the index of the product and
> the residue of the product, namely
>
> (i*30+a) * (j*30+b) / 30 (for the index)
> (i*30+a) * (j*30+b) % 30 (for the residue)
>
> Any term with a *30 in the numerator doesn't contribute to
> the residue, and also can be combined with the by-30 divide
> for computing the index. Thus these expressions can be
> rewritten as
>
> i*30*j + i*b + j*a + (a*b/30) (for the index)
> a*b%30 (for the residue)
>
> When a and b have values that are known at compile time,
> neither the divide nor the remainder result in run-time
> operations being done; all of that heavy lifting is
> optimized away and done at compile time. Of course there
> are some multiplies, but they are cheaper than divides, and
> also can be done in parallel. (The multiplication a*b also
> can be done at compile time.)
>
> The residue needs to be turned into a bit mask to do the
> logical operation on the byte of bits, but here again that
> computation can be optimized away and done at compile time.
>
> Does that all make sense?
Right now, no. But that's me. I'll flag it to read again when I've had a
better night's sleep.
Andy
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2024-01-13 21:31 -0800 |
| Message-ID | <865xzwmqf5.fsf@linuxsc.com> |
| In reply to | #118151 |
Vir Campestris <vir.campestris@invalid.invalid> writes:
> On 24/12/2023 08:36, Tim Rentsch wrote:
>
>> Depending on how the code is written, no modulo operations need
>> to be done, because they will be optimized away and done at
>> compile time. If we look at multiplying two numbers represented
>> by bits in bytes i and j, the two numbers are
>>
>> i*30 + a
>> j*30 + b
>>
>> for some a and b in { 1, 7, 11, 13 17, 19, 23, 29 }.
>>
>> The values we're interested in are the index of the product and
>> the residue of the product, namely
>>
>> (i*30+a) * (j*30+b) / 30 (for the index)
>> (i*30+a) * (j*30+b) % 30 (for the residue)
>>
>> Any term with a *30 in the numerator doesn't contribute to
>> the residue, and also can be combined with the by-30 divide
>> for computing the index. Thus these expressions can be
>> rewritten as
>>
>> i*30*j + i*b + j*a + (a*b/30) (for the index)
>> a*b%30 (for the residue)
>>
>> When a and b have values that are known at compile time,
>> neither the divide nor the remainder result in run-time
>> operations being done; all of that heavy lifting is
>> optimized away and done at compile time. Of course there
>> are some multiplies, but they are cheaper than divides, and
>> also can be done in parallel. (The multiplication a*b also
>> can be done at compile time.)
>>
>> The residue needs to be turned into a bit mask to do the
>> logical operation on the byte of bits, but here again that
>> computation can be optimized away and done at compile time.
>>
>> Does that all make sense?
>
> Right now, no. But that's me. I'll flag it to read again when I've
> had a better night's sleep.
I'm posting to nudge you into looking at this again, if
you haven't already.
I have now had a chance to get your source and run some
comparisons. A program along the lines I outlined can run much
faster than the code you posted (as well as needing less memory).
A good target is to find all primes less than 1e11, which needs
less than 4gB of ram.
[toc] | [prev] | [next] | [standalone]
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2023-12-20 13:44 +0100 |
| Message-ID | <ulunk0$iacr$1@raubtier-asyl.eternal-september.org> |
| In reply to | #118061 |
Am 11.12.2023 um 18:12 schrieb Vir Campestris:
> Because all primes except 2 are odd you don't need to store the _even_
> numbers, which is what I meant to say. Or else you only need to store
> the odd ones.
I changed the code this morning:
#include <cstdlib>
#include <charconv>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <bit>
#include <fstream>
#include <string_view>
#include <thread>
#include <utility>
#include <new>
#include <span>
#include <array>
#include <cassert>
#if defined(_MSC_VER)
#include <intrin.h>
#elif defined(__GNUC__) || defined(__clang__)
#include <cpuid.h>
#endif
#if defined(_MSC_VER)
#pragma warning(disable: 26495)
#endif
using namespace std;
#if defined(__cpp_lib_hardware_interference_size)
constexpr ptrdiff_t CL_SIZE = hardware_destructive_interference_size;
#else
constexpr ptrdiff_t CL_SIZE = 64;
#endif
size_t getL2Size();
bool smt();
int main( int argc, char **argv )
{
if( argc < 2 )
return EXIT_FAILURE;
auto parse = []( char const *str, auto &value )
{
bool hex = str[0] == '0' && (str[1] == 'x' || str[1] == 'X');
str += 2 * hex;
auto [ptr, ec] = from_chars( str, str + strlen( str ), value, !hex ?
10 : 16 );
return ec == errc() && !*ptr;
};
size_t end;
if( !parse( argv[1], end ) )
return EXIT_FAILURE;
if( end < 2 || (ptrdiff_t)end++ < 0 )
throw bad_alloc();
unsigned
hc = jthread::hardware_concurrency(),
nThreads;
if( argc < 4 || !parse( argv[3], nThreads ) )
nThreads = hc;
if( !nThreads )
return EXIT_FAILURE;
using word_t = size_t;
constexpr size_t
BITS_PER_CL = CL_SIZE * 8,
BITS = sizeof(word_t) * 8,
DBITS = 2 * BITS;
size_t nBits = end / 2 + (end & 1 ^ 1);
union alignas(CL_SIZE) ndi_words_cl { word_t words[CL_SIZE /
sizeof(word_t)]; ndi_words_cl() {} };
vector<ndi_words_cl> sieveCachelines( (nBits + BITS_PER_CL - 1) /
BITS_PER_CL );
span<word_t> sieve( &sieveCachelines[0].words[0], (nBits + BITS - 1) /
BITS );
fill( sieve.begin(), sieve.end(), (word_t)-1 );
size_t sqrt = (ptrdiff_t)ceil( ::sqrt( (ptrdiff_t)end ) );
auto punch = [&]( auto, size_t start, size_t end, size_t prime )
{
assert(start & 1);
size_t bit = start / 2;
end = end / 2 + (end & 1 ^ 1);
if( bit >= end )
return;
if( prime >= BITS ) [[likely]]
do [[likely]]
sieve[bit / BITS] &= rotl( (word_t)-2, bit % BITS );
while( (bit += prime) < end );
else
{
auto pSieve = sieve.begin() + bit / BITS;
do [[likely]]
{
word_t
word = *pSieve,
mask = rotl( (word_t)-2, bit % BITS ),
oldMask;
do
word &= mask,
oldMask = mask,
mask = rotl( mask, prime % BITS ),
bit += prime;
while( mask < oldMask );
*pSieve++ = word;
} while( bit < end );
}
};
for( size_t prime = 3; prime < sqrt; prime += 2 ) [[likely]]
{
auto pSieve = sieve.begin() + prime / DBITS;
do [[likely]]
if( word_t w = *pSieve >> prime / 2 % BITS; w ) [[likely]]
{
prime += 2 * countr_zero( w );
break;
}
while( (prime = (prime + DBITS & -(ptrdiff_t)DBITS) + 1) < sqrt );
if( prime >= sqrt ) [[unlikely]]
break;
punch( false_type(), prime * prime, sqrt, prime );
}
auto scan = [&]( size_t start, size_t end, auto fn )
{
assert(start & 1);
start /= 2;
end = end / 2 + (end & 1 ^ 1);
if( start >= end )
return;
auto pSieve = sieve.begin() + start / BITS;
for( size_t bit = start; ; )
{
word_t word = *pSieve++ >> bit % BITS;
bool hasBits = word;
for( unsigned gap; word; word >>= gap, word >>= 1 ) [[likely]]
{
gap = countr_zero( word );
if( (bit += gap) >= end ) [[unlikely]]
return;
fn( bit * 2 + 1, true_type() );
if( ++bit >= end ) [[unlikely]]
return;
}
if( bit >= end ) [[unlikely]]
break;
bit = (bit + BITS - hasBits) & -(ptrdiff_t)BITS;
}
};
static auto dbl = []( ptrdiff_t x ) { return (double)x; };
double threadTange = dbl( end - sqrt ) / nThreads;
using range_t = pair<size_t, size_t>;
vector<pair<size_t, size_t>> ranges;
ranges.reserve( nThreads );
for( size_t t = nThreads, rEnd = end, rStart; t--; rEnd = rStart )
[[likely]]
{
rStart = sqrt + (ptrdiff_t)((ptrdiff_t)t * threadTange + 0.5);
size_t rClStart = rStart & -(2 * CL_SIZE * 8);
rStart = rClStart >= sqrt ? rClStart : sqrt;
if( rStart < rEnd )
ranges.emplace_back( rStart, rEnd );
}
double maxCacheRange = dbl( getL2Size() * (8 * 2) ) / 3 * (smt() &&
nThreads > hc / 2 ? 1 : 2);
vector<jthread> threads;
threads.reserve( ranges.size() - 1 );
for( range_t const &range : ranges )
{
auto cacheAwarePunch = [&]( size_t rStart, size_t rEnd )
{
double thisThreadRange = dbl( rEnd - rStart );
ptrdiff_t nCachePartitions = (ptrdiff_t)ceil( thisThreadRange /
maxCacheRange );
double cacheRange = thisThreadRange / dbl( nCachePartitions );
for( size_t p = nCachePartitions, cacheEnd = rEnd, cacheStart; p--;
cacheEnd = cacheStart ) [[likely]]
{
cacheStart = rStart + (ptrdiff_t)((double)(ptrdiff_t)p * cacheRange
+ 0.5);
cacheStart &= -(2 * CL_SIZE * 8);
scan( 3, sqrt,
[&]( size_t prime, auto )
{
size_t start = ((cacheStart >= sqrt ? cacheStart : sqrt) + prime -
1) / prime * prime;
start = start & 1 ? start : start + prime;
punch( true_type(), start, cacheEnd, prime );
} );
}
};
if( &range != &ranges.back() )
threads.emplace_back( cacheAwarePunch, range.first, range.second );
else
cacheAwarePunch( range.first, range.second );
}
threads.resize( 0 );
if( argc >= 3 && !*argv[2] )
return EXIT_SUCCESS;
ofstream ofs;
ofs.exceptions( ofstream::failbit | ofstream::badbit );
ofs.open( argc >= 3 ? argv[2] : "primes.txt", ofstream::binary |
ofstream::trunc );
constexpr size_t
BUF_SIZE = 0x100000,
AHEAD = 32;
union ndi_char { char c; ndi_char() {} };
vector<ndi_char> rawPrintBuf( BUF_SIZE + AHEAD - 1 );
span printBuf( &rawPrintBuf.front().c, &rawPrintBuf.back().c + 1 );
auto
bufBegin = printBuf.begin(),
bufEnd = bufBegin,
bufFlush = bufBegin + BUF_SIZE;
auto print = [&]() { ofs << string_view( bufBegin, bufEnd ); };
auto printPrime = [&]( size_t prime, auto )
{
auto [ptr, ec] = to_chars( &*bufEnd, &bufEnd[AHEAD - 1], prime );
if( ec != errc() ) [[unlikely]]
throw system_error( (int)ec, generic_category(), "converson failed" );
bufEnd = ptr - &*bufBegin + bufBegin; // pointer to iterator - NOP
*bufEnd++ = '\n';
if( bufEnd >= bufFlush ) [[unlikely]]
print(), bufEnd = bufBegin;
};
printPrime( 2, false_type() );
scan( 3, end, printPrime );
print();
}
array<unsigned, 4> cpuId( unsigned code )
{
array<unsigned, 4> regs;
#if defined(_MSC_VER)
__cpuid( (int *)®s[0], code );
#elif defined(__GNUC__) || defined(__clang__)
__cpuid(code, regs[0], regs[1], regs[2], regs[3]);
#endif
return regs;
}
bool smt()
{
if( cpuId( 0 )[0] < 1 )
return false;
return cpuId( 1 )[3] >> 28 & 1;
}
size_t getL2Size()
{
if( cpuId( 0x80000000u )[0] < 0x80000006u )
return 512ull * 1024;
return (cpuId( 0x80000006u )[2] >> 16) * 1024;
}
Now the code runs 0.15s on the 16 core Zen4 system, that's +87% faster.
On th4e 64 core Zen2 system the time to produce the first 21 million
primes is about 0.05 seconds.
[toc] | [prev] | [next] | [standalone]
| From | Vir Campestris <vir.campestris@invalid.invalid> |
|---|---|
| Date | 2023-12-21 15:30 +0000 |
| Message-ID | <um1lm5$14br5$1@dont-email.me> |
| In reply to | #118088 |
On 20/12/2023 12:44, Bonita Montero wrote:
> Now the code runs 0.15s on the 16 core Zen4 system, that's +87% faster.
> On th4e 64 core Zen2 system the time to produce the first 21 million
> primes is about 0.05 seconds.
I thought I'd try it.
Can I make a suggestion? Where it says
if( argc < 2 )
return EXIT_FAILURE;
make it instead print a user guide?
On my system my code takes about 20 seconds to produce 1e9 primes. It's
single threaded. Yours is taking a little over 6, but about 18 seconds
of CPU time. (I have 4 cores, each with 2 threads. Mine is designed to
be cool and quiet...)
I've obviously got something wrong though - I'm using a _lot_ more
memory than you.
Out of interest - I thought you must be Spanish from your name. And yet
you speak fluent German?
Andy
[toc] | [prev] | [next] | [standalone]
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2023-12-21 17:07 +0100 |
| Message-ID | <um1nsg$14lai$2@raubtier-asyl.eternal-september.org> |
| In reply to | #118103 |
Am 21.12.2023 um 16:30 schrieb Vir Campestris: > Can I make a suggestion? Where it says > > if( argc < 2 ) > return EXIT_FAILURE; > > make it instead print a user guide? The code isnt for an application which is ready-to-use but just a technology experiment. > On my system my code takes about 20 seconds to produce 1e9 primes. It's > single threaded. Yours is taking a little over 6, but about 18 seconds > of CPU time. (I have 4 cores, each with 2 threads. Mine is designed to > be cool and quiet...) bg --times --high bitmapSieve 0x1000000000 "" // bg is my own tool real 2.471s user 1m:0.313s sys 0.234s cylces 273.769.270.155 As you can see my code spends an minute CPU-time in about 2.5 seconds. Interestingly the whole code largely depends on the performance of the L2 cache. If more than one of my punch-threads occupies one core there is almost no performance-improvement since both threads depend on the same L2 cache. > I've obviously got something wrong though - I'm using a _lot_ more > memory than you. I'm using a bitmap to store the odd values. > Out of interest - I thought you must be Spanish from your name. > And yet you speak fluent German? My parents come from Peru.
[toc] | [prev] | [next] | [standalone]
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2023-12-21 17:13 +0100 |
| Message-ID | <um1o7j$14ool$1@raubtier-asyl.eternal-september.org> |
| In reply to | #118103 |
Am 21.12.2023 um 16:30 schrieb Vir Campestris: > On my system my code takes about 20 seconds to produce 1e9 primes. It's > single threaded. Yours is taking a little over 6, but about 18 seconds > of CPU time. (I have 4 cores, each with 2 threads. Mine is designed to > be cool and quiet...) I forgot to mention that I'm using "" as the second commandline parameter, ich suppresses the file output. Producing a 2.2GB file from all primes that fit in a 32 bit number costs an extra two seconds for my system with a PCIe 4.0 SSD from Samsung.
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2023-12-23 10:21 -0800 |
| Message-ID | <86il4ovkz3.fsf@linuxsc.com> |
| In reply to | #118103 |
Vir Campestris <vir.campestris@invalid.invalid> writes: > On my system my code takes about 20 seconds to produce 1e9 > primes. [...] Do you mean 1e9 primes or just the primes less than 1e9? To do the first 1e9 primes a sieve would need to go up to about 23.9e9 (so half that many bits if only odd numbers were represented).
[toc] | [prev] | [next] | [standalone]
| From | Vir Campestris <vir.campestris@invalid.invalid> |
|---|---|
| Date | 2023-12-23 21:21 +0000 |
| Message-ID | <um7j0h$27ikh$2@dont-email.me> |
| In reply to | #118118 |
On 23/12/2023 18:21, Tim Rentsch wrote: > Vir Campestris <vir.campestris@invalid.invalid> writes: > >> On my system my code takes about 20 seconds to produce 1e9 >> primes. [...] > > Do you mean 1e9 primes or just the primes less than 1e9? To > do the first 1e9 primes a sieve would need to go up to about > 23.9e9 (so half that many bits if only odd numbers were > represented). Primes up to 1e9. I have another idea though, watch this space... Andy
[toc] | [prev] | [next] | [standalone]
Page 1 of 11 [1] 2 3 … 11 Next page →
Back to top | Article view | comp.lang.c++
csiph-web