# Overview

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.

# 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
```