# Overview

Atlassian Sourcetree is a free Git and Mercurial client for Windows.

Atlassian Sourcetree is a free Git and Mercurial client for Mac.

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