C#•16mo ago

❔ id love to get a code review if possible

this is a segmented sieve code I wrote. it is meant to be as fast as I can get it, however id mostly like to get coding conventions for cs down

using System.Collections;
using System.Collections.Generic;

public class Primes
{
    static List<int> primes = new List<int>(new int[] { 2, 3, 5, 7 });
    static int segment = 1;
    public static void add_next_seg()
    {
        // use segmented sieve to add numbers to the prime list.
        
        //the next primes for whom we will check the squared segment
        int start = Primes.primes[Primes.segment];
        int end = Primes.primes[Primes.segment + 1];

        //create the bounds of the segment
        int seg_start = start * start;
        int seg_end = end * end;
        //create the segment, false -> prime, true -> composite
        bool[] seg = new bool[seg_end - seg_start];
        
        //the max number is seg_end which is end**2 -> only need to check primes under and including end.
        //no need to check 2, as we will jump by 2 when adding the numbers later
        for (int i = 1; i < segment + 1; i++) {
            int prime_num = Primes.primes[i];
            //start at start of segment and mark all numbers devisible by the prime number
            for (int ind = seg_start + (prime_num - (seg_start%prime_num))%prime_num; ind - seg_start < seg.Length; ind += prime_num)
            {
                seg[ind - seg_start] = true;
            }
        }
        
        //no need to check 2, as we precoded first iteration, -> start != 2 -> seg_start is odd
        for (int ind = seg_start; ind < seg_end; ind+=2)
        {
            if (!seg[ind - seg_start])
            {
                Primes.primes.Add(ind);
            }
        }
        Primes.segment++;
    }
    public static int get_nth_prime(int ind){
        //returns the nth prime
        while (Primes.primes.Count <= ind){
            Primes.add_next_seg();
        }
        return Primes.primes[ind];
    }
}

using System.Collections;
using System.Collections.Generic;

public class Primes
{
    static List<int> primes = new List<int>(new int[] { 2, 3, 5, 7 });
    static int segment = 1;
    public static void add_next_seg()
    {
        // use segmented sieve to add numbers to the prime list.
        
        //the next primes for whom we will check the squared segment
        int start = Primes.primes[Primes.segment];
        int end = Primes.primes[Primes.segment + 1];

        //create the bounds of the segment
        int seg_start = start * start;
        int seg_end = end * end;
        //create the segment, false -> prime, true -> composite
        bool[] seg = new bool[seg_end - seg_start];
        
        //the max number is seg_end which is end**2 -> only need to check primes under and including end.
        //no need to check 2, as we will jump by 2 when adding the numbers later
        for (int i = 1; i < segment + 1; i++) {
            int prime_num = Primes.primes[i];
            //start at start of segment and mark all numbers devisible by the prime number
            for (int ind = seg_start + (prime_num - (seg_start%prime_num))%prime_num; ind - seg_start < seg.Length; ind += prime_num)
            {
                seg[ind - seg_start] = true;
            }
        }
        
        //no need to check 2, as we precoded first iteration, -> start != 2 -> seg_start is odd
        for (int ind = seg_start; ind < seg_end; ind+=2)
        {
            if (!seg[ind - seg_start])
            {
                Primes.primes.Add(ind);
            }
        }
        Primes.segment++;
    }
    public static int get_nth_prime(int ind){
        //returns the nth prime
        while (Primes.primes.Count <= ind){
            Primes.add_next_seg();
        }
        return Primes.primes[ind];
    }
}

162 Replies

potzko•16mo ago

couldn't fit the main, here it is:

using System.Diagnostics;
void main(){
    void test(int num)
    {
        Console.WriteLine("got {0} as the {1}'th prime", Primes.get_nth_prime(num), num);
    }

    Stopwatch sw = new Stopwatch();
    sw.Start();

    test(10_000_000);

    sw.Stop();
    Console.WriteLine("took {0} seconds to calc", sw.Elapsed.TotalSeconds);
}
main();

using System.Diagnostics;
void main(){
    void test(int num)
    {
        Console.WriteLine("got {0} as the {1}'th prime", Primes.get_nth_prime(num), num);
    }

    Stopwatch sw = new Stopwatch();
    sw.Start();

    test(10_000_000);

    sw.Stop();
    Console.WriteLine("took {0} seconds to calc", sw.Elapsed.TotalSeconds);
}
main();

Jimmacle•16mo ago

your naming conventions aren't what are normally used in C# you'll generally want to avoid stateful static members new List<int>(new int[] { 2, 3, 5, 7 }); technically wastes an array allocation though it's basically irrelevant for performance here

potzko•16mo ago

mind elaborating on the second point? meanwhile ill look into the naming conventions?

Jimmacle•16mo ago

static members aren't associated with any particular instance of an object which can make them hard to test and clean up for a little program like this it's fine, but maintainability can become a problem

potzko•16mo ago

I was trying to make exactly that, I only want one prime list in the class and no instantiation no constructor in the class would this name "addNextSegment" be the expected name?

Jimmacle•16mo ago

methods are always PascalCase, that's one thing that i basically never see people put different spins on local variables are camelCase, class fields are also usually camelCase but some people (like me) do _camelCase i think MS has their own code style recommendations somewhere

Jimmacle•16mo ago

https://learn.microsoft.com/en-us/dotnet/csharp/fundamentals/coding-style/coding-conventions

C# Coding Conventions

Learn about coding conventions in C#. Coding conventions create a consistent look to the code and facilitate copying, changing, and maintaining the code.

potzko•16mo ago

ty also how would you do this?

new List<int>(new int[] { 2, 3, 5, 7 });

new List<int>(new int[] { 2, 3, 5, 7 });

in rust id do

vec![2,3,5,7];

vec![2,3,5,7];

but im not sure if there is a list macro in C#

Jimmacle•16mo ago

you can just do new List<int> { 2, 3, 5, 7 };

potzko•16mo ago

oh lol, ty

Jimmacle•16mo ago

also there are no kinds of macros in C#

potzko•16mo ago

oh, so if I want something like a macro I have to do it in runtime?

Jimmacle•16mo ago

to an extent

potzko•16mo ago

wait C/C++ has macros isn't C# a superset of C++?

Jimmacle•16mo ago

not at all no pointers, for example (unless you really want them) memory is generally managed for you also everything is an object or a member of an object type, you can't have standalone functions the syntax is similar, that's about it

potzko•16mo ago

nice, thanks a lot you helped me a ton 🙂

Jimmacle•16mo ago

as for macros/templates/etc, they don't exist but there are ways you can do compile-time code generation e.g. source generators

potzko•16mo ago

reminds me of python a bit

Jimmacle•16mo ago

if you've touched java C# is essentially java but better

potzko•16mo ago

yea I figured there is a way, but it's prob a bit more advanced then what I know in C# I heard the joke of microsoft java lol

Jimmacle•16mo ago

unless i'm wrong it literally was microsoft java because they didn't want to deal with sun/oracle or something i should correct myself about no templates, c# has generic types which are similar but significantly more limited

potzko•16mo ago

I see ty

Jimmacle•16mo ago

for example List<int> is a generic List<T> specialized to hold int objects

potzko•16mo ago

yea, same as in rust

Aaron•16mo ago

oh, in here

potzko•16mo ago

hi here im potzko

Aaron•16mo ago

in, not i'm :p

potzko•16mo ago

oof lol I made public class Primes but no constructor so only one class with no instances I think

Jimmacle•16mo ago

technically no you can make as many instances if your class as you want because it isn't marked static

Aaron•16mo ago

just do public static class Primes it will stop you from ever making an instance

Jimmacle•16mo ago

but the only state you have is static, so instances wouldn't have anything "in" them IMO it would still be better to make it non-static and pass the same instance around

potzko•16mo ago

oh so because I wrote all of the data is static, it is all saved to the class, and each instance will not have any data

Jimmacle•16mo ago

right, static fields have state independent of any instance of the class

Burrito•16mo ago

You might want to check out C# naming convention as well.

potzko•16mo ago

so I can make 20 instances and they will all "point" to the same prime list

Jimmacle•16mo ago

not even that

potzko•16mo ago

yea I already changed it

Jimmacle•16mo ago

they aren't accessible on an instance of the type, only the type itself

var primes = new Primes();
primes.add_next_seg(); // this is a compiler error
Primes.add_next_seg(); // this isn't

var primes = new Primes();
primes.add_next_seg(); // this is a compiler error
Primes.add_next_seg(); // this isn't

potzko•16mo ago

because the data is not public by default right?

Jimmacle•16mo ago

that as well

Aaron•16mo ago

no, its just because you aren't allowed to do static things with an instance its like if you did

struct S;

impl S {
    pub fn thing() {}
}

fn main() {
    let s = S;
    s.thing();
}

struct S;

impl S {
    pub fn thing() {}
}

fn main() {
    let s = S;
    s.thing();
}

Burrito•16mo ago

Ah missed it.

Jimmacle•16mo ago

i don't have enough thigh-highs for this conversation anymore

potzko•16mo ago

ah I see lol

Burrito•16mo ago

Also consider var instead of explicit types:

bool[] seg = new bool[seg_end - seg_start];
// could be
var seg = new bool[seg_end - seg_start];

bool[] seg = new bool[seg_end - seg_start];
// could be
var seg = new bool[seg_end - seg_start];

Aaron•16mo ago

they said rust, so i just used the language i know they know kekw

potzko•16mo ago

oh that's nice, like let 🙂

Jimmacle•16mo ago

i'd personally avoid var until you're more familiar with the .NET BCL and generally know what types exist seen some people make mistakes because something was a type they didn't expect they were total beginners though, not coming from another language

Burrito•16mo ago

I doubt for them, Rust uses type inference heavily.

potzko•16mo ago

I think ill hardcode types untill I can write stuff on notepad that compiles then var all the way same as I did in rust

Jimmacle•16mo ago

also, might be personal preference but int ind = seg_start + (prime_num - (seg_start%prime_num))%prime_num is entirely too much to put inline with a for loop

potzko•16mo ago

is this better or worse?

for (int ind = seg_start + (prime_num - (seg_start%prime_num))%prime_num
; ind - seg_start < seg.Length
; ind += prime_num)

for (int ind = seg_start + (prime_num - (seg_start%prime_num))%prime_num
; ind - seg_start < seg.Length
; ind += prime_num)

Jimmacle•16mo ago

worse

Burrito•16mo ago

On performance side of things, I would say a simple low hanging fruit would be to give a good initial size to primes; if you know you are calculating for 10 million primes, set its size as so, so it won't be resizing all the time.

Jimmacle•16mo ago

i'd declare another variable before the loop with the calculation then just assign that to ind or declare ind outside the loop and skip initializing it

potzko•16mo ago

prob in getNthPrime right? im not sure how to do that so I let the runtime figure things out like this?

int ind = seg_start + (prime_num - (seg_start%prime_num))%prime_num;
for (; ind - seg_start < seg.Length; ind += prime_num)

int ind = seg_start + (prime_num - (seg_start%prime_num))%prime_num;
for (; ind - seg_start < seg.Length; ind += prime_num)

Jimmacle•16mo ago

i still don't really like skipping bits of the for loop but breaking it up is going in the right direction imo if i were to nitpick i'd want spacing between each operator as well

Burrito•16mo ago

Lists aren't magic, it's backed by some underlying memory; when you keep adding elements to it that the underlying memory cannot fit anymore, new chunk of memory has to be allocated and move the old stuffs over. If you know ahead of time how many elements there will be, then you having that size would prevent constant resizing and copying.

potzko•16mo ago

I like doing it based on order of operations if there are only 2 groupings, +- get a space, */ don't or +- get a space and brackets do not, depending on the line

Jimmacle•16mo ago

it's ultimately personal preference, i just wouldn't let you do it in my codebase 😛

potzko•16mo ago

yea, in rust I used .reserve I just couldn't find the equivalent in the List documentation in Microsoft's website

Aaron•16mo ago

EnsureCapacity

Jimmacle•16mo ago

you can also use the constructor with capacity

Aaron•16mo ago

well, not its not reserve, its resize

Jimmacle•16mo ago

new List<int>(initialCapacity) { elements }

potzko•16mo ago

ty, is that added, or up to? EnsureCapacity(3) -> I have 3 bytes, or I have 3 more bytes?

Aaron•16mo ago

exactly 3 or the current list count

Jimmacle•16mo ago

elements, not bytes

Aaron•16mo ago

whichever is greater

potzko•16mo ago

ty I think it matters more for stuff you are not sure about, A | B & C for example, in my opinion is less clear then A | B&C

Aaron•16mo ago

huh, i never realized how many weird unsafe methods are on Vec spare_capacity_mut is scary kekw

Jimmacle•16mo ago

i just use more parentheses until it makes sense

potzko•16mo ago

il get lisp flashbacks harold

Jimmacle•16mo ago

i mean, i also don't do a crazy amount of math on one line either

potzko•16mo ago

just add a line for each compare, and for each line say exactly what you do smh

AND B, C
OR  B, A

AND B, C
OR  B, A

Jimmacle•16mo ago

i'll break it into meaningfully named variables so i don't come back a week later and wonder WTF this equation is doing

potzko•16mo ago

Id also do it, I think that for 3-4 ops where order of operations is relevant I like to see it in code and I don't want too many parans everywhere as it makes it harder to skim through imo I updated the code I think it looks a bit weird but it might be because im used to the camel case

using System.Collections;
using System.Collections.Generic;

public static class Primes
{
    static List<int> primes = new List<int>(new int[] { 2, 3, 5, 7 });
    static int segment = 1;
    public static void addNextSegment()
    {
        // use segmented sieve to add numbers to the prime list.
        
        //the next primes for whom we will check the squared segment
        int start = Primes.primes[Primes.segment];
        int end = Primes.primes[Primes.segment + 1];

        //create the bounds of the segment
        int segStart = start * start;
        int segEnd = end * end;
        //create the segment, false -> prime, true -> composite
        bool[] seg = new bool[segEnd - segStart];
        
        //the max number is segEnd which is end**2 -> only need to check primes under and including end.
        //no need to check 2, as we will jump by 2 when adding the numbers later
        for (int i = 1; i < segment + 1; i++) {
            int primeNum = Primes.primes[i];
            //start at start of segment and mark all numbers devisible by the prime number
            int ind = segStart + (primeNum - (segStart%primeNum))%primeNum;
            for (; ind - segStart < seg.Length; ind += primeNum)
            {
                seg[ind - segStart] = true;
            }
        }
        
        //no need to check 2, as we precoded first iteration, -> start != 2 -> segStart is odd
        for (int ind = segStart; ind < segEnd; ind+=2)
        {
            if (!seg[ind - segStart])
            {
                Primes.primes.Add(ind);
            }
        }
        Primes.segment++;
    }
    public static int getNthPrime(int ind){
        //returns the nth prime
        Primes.primes.EnsureCapacity(ind);
        while (Primes.primes.Count <= ind){
            Primes.addNextSegment();
        }
        return Primes.primes[ind];
    }
}

using System.Collections;
using System.Collections.Generic;

public static class Primes
{
    static List<int> primes = new List<int>(new int[] { 2, 3, 5, 7 });
    static int segment = 1;
    public static void addNextSegment()
    {
        // use segmented sieve to add numbers to the prime list.
        
        //the next primes for whom we will check the squared segment
        int start = Primes.primes[Primes.segment];
        int end = Primes.primes[Primes.segment + 1];

        //create the bounds of the segment
        int segStart = start * start;
        int segEnd = end * end;
        //create the segment, false -> prime, true -> composite
        bool[] seg = new bool[segEnd - segStart];
        
        //the max number is segEnd which is end**2 -> only need to check primes under and including end.
        //no need to check 2, as we will jump by 2 when adding the numbers later
        for (int i = 1; i < segment + 1; i++) {
            int primeNum = Primes.primes[i];
            //start at start of segment and mark all numbers devisible by the prime number
            int ind = segStart + (primeNum - (segStart%primeNum))%primeNum;
            for (; ind - segStart < seg.Length; ind += primeNum)
            {
                seg[ind - segStart] = true;
            }
        }
        
        //no need to check 2, as we precoded first iteration, -> start != 2 -> segStart is odd
        for (int ind = segStart; ind < segEnd; ind+=2)
        {
            if (!seg[ind - segStart])
            {
                Primes.primes.Add(ind);
            }
        }
        Primes.segment++;
    }
    public static int getNthPrime(int ind){
        //returns the nth prime
        Primes.primes.EnsureCapacity(ind);
        while (Primes.primes.Count <= ind){
            Primes.addNextSegment();
        }
        return Primes.primes[ind];
    }
}

using System.Diagnostics;
void main(){
    void test(int num)
    {
        Stopwatch sw = new Stopwatch();
        sw.Start();
        int ret = Primes.getNthPrime(num);
        sw.Stop();
        Console.WriteLine("got {0} as the {1}'th prime", ret, num);
        Console.WriteLine("took {0} seconds to calc", sw.Elapsed.TotalSeconds);
    }
    test(100_000_000);
}
main();

using System.Diagnostics;
void main(){
    void test(int num)
    {
        Stopwatch sw = new Stopwatch();
        sw.Start();
        int ret = Primes.getNthPrime(num);
        sw.Stop();
        Console.WriteLine("got {0} as the {1}'th prime", ret, num);
        Console.WriteLine("took {0} seconds to calc", sw.Elapsed.TotalSeconds);
    }
    test(100_000_000);
}
main();

Jimmacle•16mo ago

second piece of code is a little misleading

potzko•16mo ago

yea I keeping the progress might add a remove primes function to the start of test

Jimmacle•16mo ago

i mean main isn't actually the entry point i forget MS's term for the program class without all the boilerplate

Jimmacle•16mo ago

https://learn.microsoft.com/en-us/dotnet/core/tutorials/top-level-templates

C# console app template changes in .NET 6+ - .NET

The .NET 6+ project template for C# console apps uses top-level statements. Understand what changed and how to use existing learning materials with the new syntax.

Aaron•16mo ago

$toplevelstatements

MODiX•16mo ago

$toplevelcode

Aaron•16mo ago

$toplevelcode

MODiX•16mo ago

Traditionally in C#, the main entry point of any program would be a static Main method (see $mains):

public static class Program
{
    public static void Main()
    {
        Console.WriteLine("Hello, world!");
    } 
}

public static class Program
{
    public static void Main()
    {
        Console.WriteLine("Hello, world!");
    } 
}

In C# 9, a feature called top-level statements was added which allows the static Main method to be omitted in favor of brevity and simplicity, and in C# 10, this was made part of the default console application template:

Console.WriteLine("Hello, world!");

Console.WriteLine("Hello, world!");

If you are following a tutorial or example code and your default template looks different, you can still write the exact same code as if you were writing it inside the static Main method. In addition, you can still write static methods inside top-level code. You can however not use top-level code in more than one file. If you wish to use the old traditional entry point, you can still use a Program class with a static Main method. https://docs.microsoft.com/en-us/dotnet/csharp/fundamentals/program-structure/top-level-statements

Top-level statements - programs without Main methods

Learn about top-level statements in C# 9 and later. You can create programs without the ceremony of a Program class and a Main method.

Aaron•16mo ago

hate it, why do we have so many tags for top level statements aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

we have $tls too

MODiX•16mo ago

$toplevelcode

Jimmacle•16mo ago

why does one tag just tell you to use the other tag

potzko•16mo ago

my god, that hello world has 13 words in it

Aaron•16mo ago

so people only have to remember to update one tag but you also can't get confused about what the tag name is and get it wrong

potzko•16mo ago

I think I can unironicly beat it in asm

Aaron•16mo ago

you can take a lot of words out tbf if you really want to

potzko•16mo ago

when I did it I just wrote Console.WriteLine("hi mom"); and it worked

Aaron•16mo ago

class Program
{
    static void Main() { Console.WriteLine("aaaa"); }
}

class Program
{
    static void Main() { Console.WriteLine("aaaa"); }
}

can go down to 7 or 8

Jimmacle•16mo ago

yeah, that's the top level statements feature you're still in the Program.Main method, it just generates all that for you by magic™️

potzko•16mo ago

automagicly oriented programing

Jimmacle•16mo ago

as a side note, that means any functions you define in a top-level statements file are local functions https://learn.microsoft.com/en-us/dotnet/csharp/programming-guide/classes-and-structs/local-functions

potzko•16mo ago

are there compiler optimization levels? or is it always maxed

Aaron•16mo ago

just debug and release default is debug, dotnet run -c Release for release

Jimmacle•16mo ago

optimization is runtime JIT magic wizardagree

the JIT will progressively optimize code paths if it thinks they're hot enough which is also why you shouldn't benchmark by just running a stopwatch around your method

potzko•16mo ago

also how bad of an idea is adding this on the last lines of addNextSegment?

seg = null;
GC.Collect();

seg = null;
GC.Collect();

Jimmacle•16mo ago

don't call the GC yourself

Aaron•16mo ago

not really a reason to but yeah, can highly recommend https://benchmarkdotnet.org/

potzko•16mo ago

here I thought C# was just an IL compiler but apparently it's a jit lol

Jimmacle•16mo ago

well something has to turn the IL into machine code

potzko•16mo ago

il check this out soon

Aaron•16mo ago

well, we have to run that IL somehow options are either interpreter or JIT and one of those options is kekw

potzko•16mo ago

can I see the IL output?

Aaron•16mo ago

yeah

Jimmacle•16mo ago

with a decompiler or built in IDE tools

Aaron•16mo ago

https://github.com/icsharpcode/ILSpy

GitHub

GitHub - icsharpcode/ILSpy: .NET Decompiler with support for PDB ge...

.NET Decompiler with support for PDB generation, ReadyToRun, Metadata (&more) - cross-platform! - GitHub - icsharpcode/ILSpy: .NET Decompiler with support for PDB generation, ReadyToRun, Me...

potzko•16mo ago

is there no -S thing?

Aaron•16mo ago

or ildasm, which comes with the sdk but uhhh ildasm is a pain there's no way to get the compiler to show it to you, no you just have to disassemble the final dll

Jimmacle•16mo ago

rider has a built in IL viewer, i'd be surprised if VS doesn't have something similar

Jimmacle•16mo ago

Jimmacle•16mo ago

you can make it do lowered C# too

Aaron•16mo ago

i don't think it does, actually it has a decompiler, never seen an IL disassembler

potzko•16mo ago

you guys were super helpfull, I think ill write another thing and call it a day, thenks a lot 🙂

Aaron•16mo ago

@potzko this is what it looks like btw

|   Method |    Count |             Mean |          Error |         StdDev |      Gen0 |      Gen1 |      Gen2 |     Allocated |
|--------- |--------- |-----------------:|---------------:|---------------:|----------:|----------:|----------:|--------------:|
| GetPrime |      100 |         1.001 us |      0.0151 us |      0.0142 us |    0.0267 |         - |         - |       2.25 KB |
| GetPrime |     1000 |        11.678 us |      0.2280 us |      0.2626 us |    0.2594 |         - |         - |      21.52 KB |
| GetPrime |  1000000 |    26,087.094 us |    340.4596 us |    284.2992 us | 2093.7500 | 1968.7500 | 1968.7500 |   26918.08 KB |
| GetPrime | 50000000 | 1,722,701.863 us | 17,190.2346 us | 16,079.7562 us | 3000.0000 | 3000.0000 | 3000.0000 | 1546235.86 KB |

|   Method |    Count |             Mean |          Error |         StdDev |      Gen0 |      Gen1 |      Gen2 |     Allocated |
|--------- |--------- |-----------------:|---------------:|---------------:|----------:|----------:|----------:|--------------:|
| GetPrime |      100 |         1.001 us |      0.0151 us |      0.0142 us |    0.0267 |         - |         - |       2.25 KB |
| GetPrime |     1000 |        11.678 us |      0.2280 us |      0.2626 us |    0.2594 |         - |         - |      21.52 KB |
| GetPrime |  1000000 |    26,087.094 us |    340.4596 us |    284.2992 us | 2093.7500 | 1968.7500 | 1968.7500 |   26918.08 KB |
| GetPrime | 50000000 | 1,722,701.863 us | 17,190.2346 us | 16,079.7562 us | 3000.0000 | 3000.0000 | 3000.0000 | 1546235.86 KB |

getting the 50 millionth prime takes about 1.7 seconds

potzko•16mo ago

I think it's keeping the progress for each run

Aaron•16mo ago

its not i made it not do that that includes allocating the list, even

potzko•16mo ago

something does not look right as it should take when written in C or rust around 3-4 seconds

Aaron•16mo ago

[MemoryDiagnoser]
public unsafe class Benchmark
{
    [Params(100, 1000, 1_000_000, 50_000_000)]
    public int Count { get; set; }
    
    [Benchmark]
    public int GetPrime()
    {
        return Primes.getNthPrime(Count);
    }
}

public static class Primes
{
    public static void addNextSegment(List<int> primes, int segment)
    {
        // use segmented sieve to add numbers to the prime list.
        
        //the next primes for whom we will check the squared segment
        int start = primes[segment];
        int end = primes[segment + 1];

        //create the bounds of the segment
        int segStart = start * start;
        int segEnd = end * end;
        //create the segment, false -> prime, true -> composite
        bool[] seg = new bool[segEnd - segStart];
        
        //the max number is segEnd which is end**2 -> only need to check primes under and including end.
        //no need to check 2, as we will jump by 2 when adding the numbers later
        for (int i = 1; i < segment + 1; i++) {
            int primeNum = primes[i];
            //start at start of segment and mark all numbers devisible by the prime number
            int ind = segStart + (primeNum - (segStart%primeNum))%primeNum;
            for (; ind - segStart < seg.Length; ind += primeNum)
            {
                seg[ind - segStart] = true;
            }
        }
        
        //no need to check 2, as we precoded first iteration, -> start != 2 -> segStart is odd
        for (int ind = segStart; ind < segEnd; ind+=2)
        {
            if (!seg[ind - segStart])
            {
                primes.Add(ind);
            }
        }
    }
    public static int getNthPrime(int ind){
        //returns the nth prime
        List<int> primes = new List<int>(ind) { 2, 3, 5, 7 };
        int segment = 1;
        while (primes.Count <= ind){
            addNextSegment(primes, segment);
            segment++;
        }
        return primes[ind];
    }
}

[MemoryDiagnoser]
public unsafe class Benchmark
{
    [Params(100, 1000, 1_000_000, 50_000_000)]
    public int Count { get; set; }
    
    [Benchmark]
    public int GetPrime()
    {
        return Primes.getNthPrime(Count);
    }
}

public static class Primes
{
    public static void addNextSegment(List<int> primes, int segment)
    {
        // use segmented sieve to add numbers to the prime list.
        
        //the next primes for whom we will check the squared segment
        int start = primes[segment];
        int end = primes[segment + 1];

        //create the bounds of the segment
        int segStart = start * start;
        int segEnd = end * end;
        //create the segment, false -> prime, true -> composite
        bool[] seg = new bool[segEnd - segStart];
        
        //the max number is segEnd which is end**2 -> only need to check primes under and including end.
        //no need to check 2, as we will jump by 2 when adding the numbers later
        for (int i = 1; i < segment + 1; i++) {
            int primeNum = primes[i];
            //start at start of segment and mark all numbers devisible by the prime number
            int ind = segStart + (primeNum - (segStart%primeNum))%primeNum;
            for (; ind - segStart < seg.Length; ind += primeNum)
            {
                seg[ind - segStart] = true;
            }
        }
        
        //no need to check 2, as we precoded first iteration, -> start != 2 -> segStart is odd
        for (int ind = segStart; ind < segEnd; ind+=2)
        {
            if (!seg[ind - segStart])
            {
                primes.Add(ind);
            }
        }
    }
    public static int getNthPrime(int ind){
        //returns the nth prime
        List<int> primes = new List<int>(ind) { 2, 3, 5, 7 };
        int segment = 1;
        while (primes.Count <= ind){
            addNextSegment(primes, segment);
            segment++;
        }
        return primes[ind];
    }
}

potzko•16mo ago

oh wait, maybe your computer is just much better

Aaron•16mo ago

ryzen 9 5900x :p

potzko•16mo ago

maybe its only deallocating the ram after it's done with the test? 1.7 seconds is insanely fast

Aaron•16mo ago

i mean, it only allocates 1.5gb per test and it can reuse that space, since the other lists disappear after its done when you get to making objects this large the GC basically just does malloc and free anyway

potzko•16mo ago

it takes 1.7 seconds with 17 seconds of error and a standard deviation of 16, something smells fishy

Aaron•16mo ago

thats not 17 seconds of error thats 17 milliseconds of error

potzko•16mo ago

oh lol welp, blazingly fast I guess 🚀

Aaron•16mo ago

i can run the rust counterpart to compare rust will probably still be a bit faster

potzko•16mo ago

one sec ill get it

Aaron•16mo ago

lets see if i can remember how the hell criterion works

potzko•16mo ago

didn't use criterion on it I think

use core::cmp::min;
use std::time;
fn main() {
    let mut prime_nums = Primes::new();
    let a = time::Instant::now();
    println!("{}", prime_nums.get(50_000_000));
    println!("{:?}", a.elapsed());
}

#[derive(Debug)]
pub struct Primes {
    prime_numbers: Vec<usize>,
    iterations: usize,
}

impl Primes {
    fn new() -> Primes {
        Primes {
            // we simulate having done the first iteration so that each segment will start with an odd number
            prime_numbers: vec![2, 3, 5, 7],
            iterations: 1,
        }
    }
    fn get(&mut self, ind: usize) -> &usize {
        self.prime_numbers.reserve(ind);
        while !(ind < self.prime_numbers.len()) {
            add_next_seg(&mut self.prime_numbers, &mut self.iterations)
        }
        &self.prime_numbers[ind]
    }
}

//this const was fast on my computer, you should mess around with it
const MAX_JUMP: usize = 1;
fn add_next_seg(primes: &mut Vec<usize>, iterations: &mut usize) {
    let seg_size = min(MAX_JUMP, primes.len() - *iterations - 1);
    let start = *iterations;
    let end = start + seg_size;
    let seg_end = primes[end].pow(2);
    let seg_start = primes[start].pow(2);
    let mut primeness = vec![true; seg_end - seg_start];
    for i in 1..=end {
        let known_prime = primes[i];
        for not_prime in
            (seg_start + (known_prime - seg_start % known_prime)..seg_end).step_by(known_prime)
        {
            primeness[not_prime - seg_start] = false;
        }
        if seg_start % known_prime == 0 {
            primeness[0] = false;
        }
    }
    /* 
    primes.reserve(
        ((seg_end as f32 / ((seg_end as f32).ln()))
            - (seg_start as f32 / ((seg_start as f32).ln()))) as usize,
    );*/
    for i in (0..primeness.len()).step_by(2) {
        if primeness[i] {
            primes.push(seg_start + i)
        }
    }
    *iterations = end;
}

use core::cmp::min;
use std::time;
fn main() {
    let mut prime_nums = Primes::new();
    let a = time::Instant::now();
    println!("{}", prime_nums.get(50_000_000));
    println!("{:?}", a.elapsed());
}

#[derive(Debug)]
pub struct Primes {
    prime_numbers: Vec<usize>,
    iterations: usize,
}

impl Primes {
    fn new() -> Primes {
        Primes {
            // we simulate having done the first iteration so that each segment will start with an odd number
            prime_numbers: vec![2, 3, 5, 7],
            iterations: 1,
        }
    }
    fn get(&mut self, ind: usize) -> &usize {
        self.prime_numbers.reserve(ind);
        while !(ind < self.prime_numbers.len()) {
            add_next_seg(&mut self.prime_numbers, &mut self.iterations)
        }
        &self.prime_numbers[ind]
    }
}

//this const was fast on my computer, you should mess around with it
const MAX_JUMP: usize = 1;
fn add_next_seg(primes: &mut Vec<usize>, iterations: &mut usize) {
    let seg_size = min(MAX_JUMP, primes.len() - *iterations - 1);
    let start = *iterations;
    let end = start + seg_size;
    let seg_end = primes[end].pow(2);
    let seg_start = primes[start].pow(2);
    let mut primeness = vec![true; seg_end - seg_start];
    for i in 1..=end {
        let known_prime = primes[i];
        for not_prime in
            (seg_start + (known_prime - seg_start % known_prime)..seg_end).step_by(known_prime)
        {
            primeness[not_prime - seg_start] = false;
        }
        if seg_start % known_prime == 0 {
            primeness[0] = false;
        }
    }
    /* 
    primes.reserve(
        ((seg_end as f32 / ((seg_end as f32).ln()))
            - (seg_start as f32 / ((seg_start as f32).ln()))) as usize,
    );*/
    for i in (0..primeness.len()).step_by(2) {
        if primeness[i] {
            primes.push(seg_start + i)
        }
    }
    *iterations = end;
}

had to cut documentation to fit it in here lol

Aaron•16mo ago

a hair faster

potzko•16mo ago

your computer is fast

Jimmacle•16mo ago

|   Method |    Count |             Mean |          Error |         StdDev |       Gen0 |      Gen1 |      Gen2 |     Allocated |
|--------- |--------- |-----------------:|---------------:|---------------:|-----------:|----------:|----------:|--------------:|
| GetPrime |      100 |         1.694 us |      0.0334 us |      0.0435 us |     0.5493 |         - |         - |       2.25 KB |
| GetPrime |     1000 |        21.504 us |      0.2299 us |      0.2038 us |     5.2490 |         - |         - |      21.52 KB |
| GetPrime |  1000000 |    33,927.243 us |    417.4607 us |    370.0680 us |  4666.6667 | 1933.3333 | 1933.3333 |    26916.2 KB |
| GetPrime | 50000000 | 2,324,728.550 us | 31,809.6145 us | 28,198.3947 us | 11000.0000 | 3000.0000 | 3000.0000 | 1546234.55 KB |

|   Method |    Count |             Mean |          Error |         StdDev |       Gen0 |      Gen1 |      Gen2 |     Allocated |
|--------- |--------- |-----------------:|---------------:|---------------:|-----------:|----------:|----------:|--------------:|
| GetPrime |      100 |         1.694 us |      0.0334 us |      0.0435 us |     0.5493 |         - |         - |       2.25 KB |
| GetPrime |     1000 |        21.504 us |      0.2299 us |      0.2038 us |     5.2490 |         - |         - |      21.52 KB |
| GetPrime |  1000000 |    33,927.243 us |    417.4607 us |    370.0680 us |  4666.6667 | 1933.3333 | 1933.3333 |    26916.2 KB |
| GetPrime | 50000000 | 2,324,728.550 us | 31,809.6145 us | 28,198.3947 us | 11000.0000 | 3000.0000 | 3000.0000 | 1546234.55 KB |

2700x

potzko•16mo ago

on mine it takes 5 seconds

Aaron•16mo ago

~1.63s without lto (forgot i had it on in this project)

potzko•16mo ago

what is lto?

Aaron•16mo ago

https://doc.rust-lang.org/cargo/reference/profiles.html#lto

Profiles - The Cargo Book

potzko•16mo ago

ah that thing

Aaron•16mo ago

basically just means it made optimizations between std and the running crate, in this case

potzko•16mo ago

yea

Aaron•16mo ago

i just noticed that get returns a &usize here, lmao

potzko•16mo ago

im lazy also I can't get your benchmark to run, I did dotnet add package BenchmarkDotNet added some using statements and then dotnet run -c Release and it's saying there is no main am I missing something?

Aaron•16mo ago

yeah

public static unsafe class Program
{
    public static void Main()
    {
        BenchmarkRunner.Run<Benchmark>();
    }
}

public static unsafe class Program
{
    public static void Main()
    {
        BenchmarkRunner.Run<Benchmark>();
    }
}

potzko•16mo ago

ah I see ty

Aaron•16mo ago

didnt send it earlier since it was in a different place in the file you can also get rid of unsafe there, lmao this project has a ton of random shit in it everywhere since its my scratchpad

potzko•16mo ago

I was scared to touch your code so I just added <AllowUnsafeBlocks>true</AllowUnsafeBlocks>

Aaron•16mo ago

$allowunsafe

MODiX•16mo ago

https://cdn.discordapp.com/attachments/569261465463160900/1057525656222703686/become_as_gods.mp4

potzko•16mo ago

lmao

|   Method |    Count |             Mean |          Error |         StdDev |       Gen0 |      Gen1 |      Gen2 |     Allocated |
|--------- |--------- |-----------------:|---------------:|---------------:|-----------:|----------:|----------:|--------------:|
| GetPrime |      100 |         1.754 us |      0.0316 us |      0.0295 us |     0.4883 |    0.0019 |         - |       2.25 KB |
| GetPrime |     1000 |        25.792 us |      0.5077 us |      0.4749 us |     4.6692 |    0.1526 |         - |      21.52 KB |
| GetPrime |  1000000 |    41,668.679 us |    129.2386 us |    114.5666 us |  4384.6154 | 1923.0769 | 1923.0769 |   26916.76 KB |
| GetPrime | 50000000 | 3,291,120.340 us | 23,944.1608 us | 22,397.3829 us | 10000.0000 | 3000.0000 | 3000.0000 | 1546246.59 KB |

|   Method |    Count |             Mean |          Error |         StdDev |       Gen0 |      Gen1 |      Gen2 |     Allocated |
|--------- |--------- |-----------------:|---------------:|---------------:|-----------:|----------:|----------:|--------------:|
| GetPrime |      100 |         1.754 us |      0.0316 us |      0.0295 us |     0.4883 |    0.0019 |         - |       2.25 KB |
| GetPrime |     1000 |        25.792 us |      0.5077 us |      0.4749 us |     4.6692 |    0.1526 |         - |      21.52 KB |
| GetPrime |  1000000 |    41,668.679 us |    129.2386 us |    114.5666 us |  4384.6154 | 1923.0769 | 1923.0769 |   26916.76 KB |
| GetPrime | 50000000 | 3,291,120.340 us | 23,944.1608 us | 22,397.3829 us | 10000.0000 | 3000.0000 | 3000.0000 | 1546246.59 KB |

your computer is fast lol

Aaron•16mo ago

¯\_(ツ)_/¯ whats your CPU

potzko•16mo ago

i5-8400 but I think it's more of a ram bottleneck when I threaded the rust code I got almost no speedup

Aaron•16mo ago

i'm not sure this can be threaded very well anyway you need to know all previous primes, don't you?

potzko•16mo ago

up to root, so after 2 iterations you are free to thread 4 cores forever

Aaron•16mo ago

potzko•16mo ago

or within the function you can thread this loop

      for (int i = 1; i < segment + 1; i++) {
            int primeNum = primes[i];
            //start at start of segment and mark all numbers devisible by the prime number
            int ind = segStart + (primeNum - (segStart%primeNum))%primeNum;
            for (; ind - segStart < seg.Length; ind += primeNum)
            {
                seg[ind - segStart] = true;
            }
        }

      for (int i = 1; i < segment + 1; i++) {
            int primeNum = primes[i];
            //start at start of segment and mark all numbers devisible by the prime number
            int ind = segStart + (primeNum - (segStart%primeNum))%primeNum;
            for (; ind - segStart < seg.Length; ind += primeNum)
            {
                seg[ind - segStart] = true;
            }
        }

Aaron•16mo ago

fair enough

Accord•16mo ago

Was this issue resolved? If so, run /close - otherwise I will mark this as stale and this post will be archived until there is new activity.

Gaming

Programming

❔ id love to get a code review if possible