C#•2y 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

potzkoOP•2y 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•2y 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

potzkoOP•2y ago

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

Jimmacle•2y 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

potzkoOP•2y 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•2y 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•2y 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.

potzkoOP•2y 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•2y ago

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

potzkoOP•2y ago

oh lol, ty

Jimmacle•2y ago

also there are no kinds of macros in C#

potzkoOP•2y ago

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

Jimmacle•2y ago

to an extent

potzkoOP•2y ago

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

Jimmacle•2y 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

potzkoOP•2y ago

nice, thanks a lot you helped me a ton 🙂

Jimmacle•2y 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

potzkoOP•2y ago

reminds me of python a bit

Jimmacle•2y ago

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

potzkoOP•2y 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•2y 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

potzkoOP•2y ago

I see ty

Jimmacle•2y ago

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

potzkoOP•2y ago

yea, same as in rust

Aaron•2y ago

oh, in here

potzkoOP•2y ago

hi here im potzko

Aaron•2y ago

in, not i'm :p

potzkoOP•2y ago

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

Jimmacle•2y ago

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

Aaron•2y ago

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

Jimmacle•2y 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

potzkoOP•2y 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•2y ago

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

Burrito•2y ago

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

potzkoOP•2y ago

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

Jimmacle•2y ago

not even that

potzkoOP•2y ago

yea I already changed it

Jimmacle•2y 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

potzkoOP•2y ago

because the data is not public by default right?

Jimmacle•2y ago

that as well

Aaron•2y 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•2y ago

Ah missed it.

Jimmacle•2y ago

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

potzkoOP•2y ago

ah I see lol

Burrito•2y 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•2y ago

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

potzkoOP•2y ago

oh that's nice, like let 🙂

Jimmacle•2y 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•2y ago

I doubt for them, Rust uses type inference heavily.

potzkoOP•2y 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•2y 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

potzkoOP•2y 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•2y ago

worse

Burrito•2y 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•2y 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

potzkoOP•2y 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•2y 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•2y 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.

potzkoOP•2y 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•2y ago

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

potzkoOP•2y ago

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

Aaron•2y ago

EnsureCapacity

Jimmacle•2y ago

you can also use the constructor with capacity

Aaron•2y ago

well, not its not reserve, its resize

Jimmacle•2y ago

new List<int>(initialCapacity) { elements }

potzkoOP•2y ago

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

Aaron•2y ago

exactly 3 or the current list count

Jimmacle•2y ago

elements, not bytes

Aaron•2y ago

whichever is greater

potzkoOP•2y 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•2y ago

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

Jimmacle•2y ago

i just use more parentheses until it makes sense

potzkoOP•2y ago

il get lisp flashbacks harold

Jimmacle•2y ago

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

potzkoOP•2y 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•2y 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

potzkoOP•2y 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•2y ago

second piece of code is a little misleading

potzkoOP•2y ago

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

Jimmacle•2y ago

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

Jimmacle•2y 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•2y ago

$toplevelstatements

MODiX•2y ago

$toplevelcode

Aaron•2y ago

$toplevelcode

MODiX•2y 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•2y ago

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

we have $tls too

MODiX•2y ago

$toplevelcode

Jimmacle•2y ago

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

potzkoOP•2y ago

my god, that hello world has 13 words in it

Aaron•2y 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

potzkoOP•2y ago

I think I can unironicly beat it in asm

Aaron•2y ago

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

potzkoOP•2y ago

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

Aaron•2y 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•2y 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™️

potzkoOP•2y ago

automagicly oriented programing

Jimmacle•2y 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

potzkoOP•2y ago

are there compiler optimization levels? or is it always maxed

Aaron•2y ago

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

Jimmacle•2y 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

potzkoOP•2y 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•2y ago

don't call the GC yourself

Aaron•2y ago

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

potzkoOP•2y ago

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

Jimmacle•2y ago

well something has to turn the IL into machine code

potzkoOP•2y ago

il check this out soon

Aaron•2y ago

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

potzkoOP•2y ago

can I see the IL output?

Aaron•2y ago

yeah

Jimmacle•2y ago

with a decompiler or built in IDE tools

Aaron•2y 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...

potzkoOP•2y ago

is there no -S thing?

Aaron•2y 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•2y ago

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

Jimmacle•2y ago

Jimmacle•2y ago

you can make it do lowered C# too

Aaron•2y ago

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

potzkoOP•2y ago

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

Aaron•2y 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

potzkoOP•2y ago

I think it's keeping the progress for each run

Aaron•2y ago

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

potzkoOP•2y ago

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

Aaron•2y 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];
    }
}

potzkoOP•2y ago

oh wait, maybe your computer is just much better

Aaron•2y ago

ryzen 9 5900x :p

potzkoOP•2y ago

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

Aaron•2y 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

potzkoOP•2y ago

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

Aaron•2y ago

thats not 17 seconds of error thats 17 milliseconds of error

potzkoOP•2y ago

oh lol welp, blazingly fast I guess 🚀

Aaron•2y ago

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

potzkoOP•2y ago

one sec ill get it

Aaron•2y ago

lets see if i can remember how the hell criterion works

potzkoOP•2y 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•2y ago

a hair faster

potzkoOP•2y ago

your computer is fast

Jimmacle•2y 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

potzkoOP•2y ago

on mine it takes 5 seconds

Aaron•2y ago

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

potzkoOP•2y ago

what is lto?

Aaron•2y ago

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

Profiles - The Cargo Book

potzkoOP•2y ago

ah that thing

Aaron•2y ago

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

potzkoOP•2y ago

yea

Aaron•2y ago

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

potzkoOP•2y 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•2y 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>();
    }
}

potzkoOP•2y ago

ah I see ty

Aaron•2y 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

potzkoOP•2y ago

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

Aaron•2y ago

$allowunsafe

MODiX•2y ago

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

potzkoOP•2y 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•2y ago

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

potzkoOP•2y 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•2y ago

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

potzkoOP•2y ago

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

Aaron•2y ago

potzkoOP•2y 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•2y ago

fair enough

Accord•2y 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