Performance issues with sequence handling, bug?

[benthor]

Hi! Wren is a great little language! (And I say this despite my strong background in Lua...)

I've had some fun trying out various approaches of the Sieve of Eratosthenes to find prime numbers, when I noticed something odd.

Most sieve implementations tend to speed up as they fill up the range. One Example is the following list-based code:

var sieve = List.filled(99999998, true)

for (i in 2...sieve.count) {
        if (sieve[i]) {
                System.print(i)
                var mult = i
                while (mult < sieve.count) {
                        sieve[mult] = false
                        mult = mult + i
                }
        }
}

When you run this, you'll notice how the first few primes take a while to print, before execution speeds up and the numbers come faster and faster.

With the following sequence-based implementation, it's the other way around however:

var seq = 2..99999997

while (!seq.isEmpty) { 
        //don't know a better way to peek at the first element in a sequence
        var elem=seq.take(1).toList[0] 
        System.print(elem)
        seq = seq.where{ |n| n % elem != 0 }
}

Something is very wrong with the output speed of that code. It starts printing quite quickly but then it slows to a crawl. Any ideas?

I'm using wren 0.4.0 on x86_64 Linux.

[mhermier]

List.filled allocate, while Seq does not. Because the allocated list is huge, it takes a little while to initialize the buffer. In addition each garbage collection take some time to traverse that list. Unless I miss read, it allocates a 100M référence array, which is a little bit less than 1Gb. So it is expected to be slow to fully initialise.

[benthor]

The problem is not in the slow initialization. It's in the fact that the sequence code slows down to a crawl as the algorithm proceeds, even though seq gets shorter and shorter with each prime number that is found: seq = seq.where{ |n| n % elem != 0 }. Instead, it should speed up significantly after the first few primes have been found. And indeed, this is what happens in the first code example I gave, leading me to suspect that either

• I'm using sequences wrong
• There is a bug in wren that affects sequence handling performance

[ruby0x1]

Thanks for the code to test, we'll take a look.

I'd be curious what happens without the System.print in there, to rule out some kinda logging slowdown.

[mhermier]

Oh wait, the second also allocate as hell and each loop. seq.take(1).toList allocate at least 2 objects, the view and the List. seq = seq.where{ |n| n % elem != 0 } create a tower of views. It is normal it slows down.

[mhermier]

I have an implementation of it somewhere, but if you want something relatively efficient, you want a mix of the 2. Some kind of memorisation, in an array/set/map of all the primes known so far up to an upper bound, and a generator part that use the known primes to populate the prime and increase the upper bound. I think there is an optimisation/trick can be used to limit the checks to less than sqrt of the upper bound. It reduce a little bit of computation, for "free".

[benthor]

Okay, do I understand this correctly

• seq = seq.where{ |n| n % elem != 0} creates a new WhereSequence on top of the previous sequence
• The documentation states:

  The returned sequence is lazy. It only applies the filtering when you iterate over the sequence, and it does so by holding a reference to the original sequence.

• Upon iteration, the references in the WhereSequence are just looked up but not collapsed, so a new WhereSequence on an existing WhereSequence has to re-follow all internal references down to the original sequence.
• The slowdown I perceive is the result of chains of references becoming longer and longer, into the tens of thousands in this case.

I've had a look at how WhereSequence is implemented and came up with a modification that caches values once they were looked up. This makes things much more snappy, easily reaching the first 10k primes within a few seconds.

class CachingWhereSequence is Sequence {
        construct new(sequence, fn) {
                _sequence = sequence
                _fn = fn 
                _cache = []
                _max = -1
                _iter = null
        } 

        iterate(iterator) { 
                if (!_sequence) { 
                        if (_max >= 0 && (!iterator || iterator < _max+1)) return iterator+1
                } else { 
                        iterator = _iter 
                        while (iterator = _sequence.iterate(iterator)) {
                                var value = _sequence.iteratorValue(iterator)
                                if (_fn.call(value)) { 
                                        _cache.add(value) 
                                        _max = _max + 1 
                                        _iter = iterator 
                                        return _max 
                                } 
                        } 
                } 
                return false 
        } 

        iteratorValue(iterator) { _cache[iterator] } 
} 

var seq = 2..99999997 
while (!seq.isEmpty) { 
        var prime=seq.take(1).toList[0]
        System.print(prime) 
        seq = CachingWhereSequence.new(seq, Fn.new {|n| n % prime != 0})
}

However, the lazy evaluation still causes construction of a large recursive tower, creating cache lists at each level. Unsurprisingly, this code runs out of memory on my machine, after about 100k primes or so.

[benthor]

I found a much leaner optimization of WhereSequence than the cache list above. I opened a PR :) #1201