Warning

This post was published 31 days ago. The information described in this article may have changed.

Info

This post is auto-generated from RSS feed The Rust Programming Language Forum - Latest topics. Source: Is Nim faster than Rust?

I thought to compare this both languages in twin_primes as I don't trust Online benchmark so I tried to test 500k twin prime numbers test segmented :

The rust code :

%%bash
cat << 'EOF' > twin_primes_segmented.rs
// twin_primes_segmented.rs
use std::time::Instant;

fn simple_sieve(limit: usize) -> Vec<bool> {
    let mut is_prime = vec![true; limit + 1];
    is_prime[0] = false;
    if limit >= 1 {
        is_prime[1] = false;
    }

    for i in 2..=((limit as f64).sqrt() as usize) {
        if is_prime[i] {
            for j in ((i * i)..=limit).step_by(i) {
                is_prime[j] = false;
            }
        }
    }
    is_prime
}

fn segmented_sieve(start: usize, end: usize, base_primes: &[usize]) -> Vec<bool> {
    let size = end - start + 1;
    let mut is_prime = vec![true; size];

    for &prime in base_primes {
        let start_idx = std::cmp::max(prime * prime, ((start + prime - 1) / prime) * prime);

        for j in (start_idx..=end).step_by(prime) {
            if j >= start {
                is_prime[j - start] = false;
            }
        }
    }

    is_prime
}

fn find_twin_primes(target_count: usize) -> f64 {
    let start_time = Instant::now();

    let sqrt_limit = 1_000_000; // Adjust as needed
    let base_primes_sieve = simple_sieve(sqrt_limit);
    let base_primes: Vec<usize> = (2..=sqrt_limit).filter(|&i| base_primes_sieve[i]).collect();

    let mut count = 0;
    let mut prev_prime = 3;
    let mut current_segment_start = 3;
    let segment_size = 1_000_000;

    loop {
        let segment_end = std::cmp::min(current_segment_start + segment_size - 1, 50_000_000); // Upper bound

        let segment_primes = segmented_sieve(current_segment_start, segment_end, &base_primes);

        for i in 0..segment_primes.len() {
            if segment_primes[i] && current_segment_start + i >= 3 {
                let candidate = current_segment_start + i;
                if candidate - prev_prime == 2 {
                    count += 1;
                    if count == target_count {
                        return start_time.elapsed().as_secs_f64();
                    }
                }
                prev_prime = candidate;
            }
        }

        current_segment_start = segment_end + 1;
        if current_segment_start > 50_000_000 {
            break;
        }
    }

    start_time.elapsed().as_secs_f64()
}

fn main() {
    let elapsed = find_twin_primes(500000);
    println!("{}", elapsed);
}
EOF

And compilation :
%%bash
source $HOME/.cargo/env

rustc -O twin_primes_segmented.rs
./twin_primes_segmented

The result for rust :
0.827 second
Subsequent run :
0.57 then saturated at 0.54 second

---

Then I tried with Nim also :

%%bash
cat << 'EOF' > twin_primes_segmented.nim
# twin_primes_segmented.nim
import times, math

const
  SegmentSize = 1_000_000
  MaxN = 50_000_000

# Simple sieve (correct)
proc simpleSieve(limit: int): seq[int] =
  var isPrime = newSeq[bool](limit + 1)
  for i in 2..limit:
    isPrime[i] = true

  for i in 2..int(sqrt(float(limit))):
    if isPrime[i]:
      for j in countup(i * i, limit, i):
        isPrime[j] = false

  for i in 2..limit:
    if isPrime[i]:
      result.add(i)

# Segmented sieve
proc segmentedSieve(start, endN: int, basePrimes: seq[int]): seq[uint8] =
  let size = endN - start + 1
  result = newSeq[uint8](size)
  for i in 0..<size:
    result[i] = 1

  for p in basePrimes:
    let p2 = p * p
    if p2 > endN:
      break

    var j = max(p2, ((start + p - 1) div p) * p)
    while j <= endN:
      result[j - start] = 0
      j += p

# Twin primes
proc findTwinPrimes(targetCount: int): float =
  let startTime = epochTime()

  let baseLimit = int(sqrt(float(MaxN)))
  let basePrimes = simpleSieve(baseLimit)

  var count = 0
  var prevPrime = 3
  var segmentStart = 3

  while segmentStart <= MaxN:
    let segmentEnd = min(segmentStart + SegmentSize - 1, MaxN)
    let segment = segmentedSieve(segmentStart, segmentEnd, basePrimes)

    for i in 0..<segment.len:
      if segment[i] == 1:
        let p = segmentStart + i
        if p >= 3:
          if p - prevPrime == 2:
            inc count
            if count == targetCount:
              return epochTime() - startTime
          prevPrime = p

    segmentStart = segmentEnd + 1

  epochTime() - startTime

let elapsed = findTwinPrimes(500_000)
echo elapsed
EOF

Compilation :
%%bash
export PATH=$HOME/.nimble/bin:$PATH

nim c -d:release
--opt:speed
--checks:off
--assertions:off
--overflowChecks:off
twin_primes_segmented.nim

./twin_primes_segmented

The Results :
0.73 second on first run
0.25 second on subsequent run then saturated at 0.23 second

From the test based on Speed the nim appears to be clear winner in this case,
Nim actually even made very small binary
Nim seems to have simple small compiler yet won the race I was amazed by Nim performance yet so simple and easy code and expressive.

Or is there problem in my code ?

2 posts - 2 participants

Read full topic

🏷️ Rust_feed