HTTPS SSH

I am recently getting interested in Generator/Coroutine, and I explored its support in several languages that I personally like. C and Go do not have Coroutine support, I use Block in C and Goroutine/Channel in Go to simulate Generator. To get a real feel of how Generator works, I go ahead implement Sieve of Eratosthenes Alogorithm to find first 10,000 prime numbers with Generator in these languages. Then, I compared their performances on my laptop, and I was surprised by the numbers. To find first 10,000 prime numbers, it took C implementation 0.501 seconds, Go Implementation 8.915 seconds, Python implementation 10.850 seconds, Ruby implementation 481.470 seconds and Kotlin implementation 2034.561 seconds! Of course, I must have done something wrong, but it's not obvious to me. I thought it worths to share the numbers, and hopefully someone can shed some light.

Update: I think I know what's going on. On the bottom of the link, it states "The operation is terminal". However, Kotlin's Sequence could be iterated multiple times, so my implementation gives correct prime numbers, except that the Sequence will have to start from the beginning. So Kotlin's Sequence is like Java8 stream, except that it could be iterated multiple times, which could be a bad thing or good thing.

A quick fix by replacing sequence with iterator give a run time of 2 seconds, which is more expected. Note that there are many ways to improve the naive algorithm, but that's not the point. The point is to compare how Generator/Coroutine works in different languages that I like. The fixed Kotlin version is listed as prime_gen.kt below.

Update: add link to Reddit discussion - https://www.reddit.com/r/programming/comments/9v3gth/it_took_kotlin_2034561_seconds_and_c_0501_seconds/

Implementation

C Implementation

#include <stdio.h>
#include <Block.h>
typedef int (^Sieve)();

Sieve make_sieve(Sieve src, int prime) {
    return Block_copy( ^(void) {
        int next;
        for (next = src(); next % prime == 0; next = src()) {}
        return next;
    });
}

Sieve make_numbers() {
    __block int i = 2;
    return Block_copy( ^(void) {
        return i++;
    });
}

int main(void) {
    Sieve sieves[10000];
    Sieve sieve = make_numbers();
    int prime;
    for (int i = 0; i < 10000; i++) { 
        sieves[i] = sieve;
        prime = sieve();
        printf("%d\n", prime);
        sieve = make_sieve(sieve, prime);
    }

    for (int i = 0; i < 10000; i++) { 
        Block_release(sieves[i]);
    }
    return 0;
}

Go Implementation

package main

func Source(ch chan<- int) {
    for i := 2; ; i++ {
        ch <- i
    }
}

func Sieve(src <-chan int, dst chan<- int, prime int) {
    for {
        i := <-src
        if i%prime != 0 {
            dst <- i
        }
    }
}

func main() {
    ch := make(chan int)
    go Source(ch)
    limit := 10000
    for {
        prime := <-ch
        println(prime)
        ch1 := make(chan int)
        go Sieve(ch, ch1, prime)
        ch = ch1
        limit -= 1
        if limit == 0 {
            break
        }
    }
}

Python Implementation

def make_sieve(src, number):
    return (n for n in src if n % number)

def source(first=1):
    while True:
        yield first
        first += 1

def primes():
    sieve = source(2)
    while True:
        prime = next(sieve)
        yield prime
        sieve = make_sieve(sieve, prime)

import sys
sys.setrecursionlimit(10**6)

import itertools
ten_thousand_primes = itertools.islice(primes(), 10000)
for n in ten_thousand_primes: print(n)

Ruby Implementation

def make_sieve(src, prime)
  Enumerator.new do |y|
    loop do
      next_prime = src.next
      y << next_prime if next_prime % prime != 0
    end 
  end
end

def primes
  sieve = (2..Float::INFINITY).lazy
  Enumerator.new do |y|
    loop do
      prime  = sieve.next
      y << prime
      sieve = make_sieve(sieve, prime)
    end
  end
end

primes.lazy.take(10000).each {|n| puts n}

Kotlin Implementation

fun main(args: Array<String>) {
    fun make_sieve(src: Sequence<Int>, prime: Int) = src.filter { it % prime != 0 }
    var sieve = sequence {
        var x = 2
        while (true) yield(x++)
    }
    for (i in 1..10000) {
        val prime = sieve.first()
        println(prime)
        sieve = make_sieve(sieve, prime)
    }
}

Kotlin (fixed) Implementation

fun main(args: Array<String>) {
    fun make_sieve(src: Iterator<Int>, prime: Int) = iterator {
        for (n in src) {
            if (n % prime != 0) yield(n)
        }
    }
    var sieve = iterator {
        var x = 2
        while (true) yield(x++)
    }
    for (i in 1..10000) {
        val prime = sieve.next()
        println(prime)
        sieve = make_sieve(sieve, prime)
    }
}

Performance

C Performance

  • 0.501 seconds
> clang -fblocks  -o prime_c prime.c
> time ./prime_c &>/dev/null

real    0m0.501s
user    0m0.490s
sys     0m0.006s

Go1.11 Performance

  • 8.915 seconds
> go build -o prime_go prime.go
> time ./prime_go &>/dev/null

real    0m8.915s
user    0m31.161s
sys     0m0.227s

Python3.6 Performance

  • 10.850 seconds
> time python3 prime.py &>/dev/null

real    0m10.850s
user    0m10.739s
sys     0m0.066s

Ruby2.4 Performance

  • 481.470 seconds
> time ruby prime.rb &>/dev/null

real    8m1.470s
user    7m46.913s
sys     0m3.977s

Kotlin1.3 Performance

  • 2034.561 seconds
> kotlinc prime.kt -include-runtime -d prime_kt.jar
> time java -jar prime_kt.jar &>/dev/null

real    33m54.561s
user    33m18.257s
sys     0m11.193s

Kotlin1.3 Performance (fixed)

  • 2.008 seconds
> kotlinc prime_gen.kt -include-runtime -d prime_gen_kt.jar
> time java -jar prime_gen_kt.jar &>/dev/null

real    0m2.008s
user    0m2.184s
sys     0m0.220s