A small benchmark experiment

84 views

Skip to first unread message

Chi-jong Shum cheng

unread,

Dec 5, 2015, 8:43:52 PM12/5/15

to picat...@googlegroups.com

A Comparison of Python, Haskell, and Picat on Reversing Linked Lists

by Chi-Jong Shum Cheng, Last Edited: 12/05/2015

This small experiment compares Python, Haskell and Picat on how fast they reverse linked-lists. For a consistent comparison, we only look at the run-time of their byte code interpreters. Two different implementations are used for reversing linked lists: naive-reverse and tail-recursion. Since Haskell and Picat’s lists are linked-lists while Python’s lists are arrays, for Python nested-tuples are used instead of regular lists in Python.

Results on naive-reverse:

List Size	Python	Haskell	Picat
1,000	1.171	Too Fast	Too Fast
10,000	36.251	Too Fast	0.797
100,000	Too Slow	0.156	80.909
1,000,000	Too Slow	1.328	Too Slow
10,000,000	Stack Overflow	14.375	Too Slow

Python is the slowest using naive-recursion while Haskell is the fastest. Both Python and Picat take O(n^2) time to reverse a list of length n, while Haskell demonstrates linear-time complexity. This is probably due to an optimization implemented by the Haskell compiler.

Results on tail-recursive reverse:

List Size	Python	Haskell	Picat
100,000	0.122	Too Fast	Too Fast
1,000,000	1.46	0.547	0.031
10,000,000	Stack Overflow	6.219	0.328

The tail-recursive version is faster than the naïve version for all three languages. Even for Haskell, tail-recursion is about twice as fast as the naïve reverse. As can be seen, the time complexity for tail-recursion is linear for all three languages. Python is still the slowest. Picat, on the other hand, is significantly faster than Haskell (more than 10 times faster).

Implementations:

# Python Implementation of Reverse

import threading, sys, time

# naive reverse for nested-tuples

def naive_reverse_nt(nt):

if nt == ():

return ()

else:

(head_single, tail_group) = nt

return concat_nt(naive_reverse_nt(tail_group), (head_single, ()))

#edef

# caller of the tail recursive reverse

def tailend_reverse_nt(nt):

return tailend_reverse_nt_aux(nt, ())

#edef

# tail recursive reverse for nested tuples

def tailend_reverse_nt_aux(nt, acc):

if nt == ():

return acc

else:

(head_single, tail_group) = nt

return tailend_reverse_nt_aux(tail_group, (head_single, acc))

#edef

# creates a nested-tuple of a given size

def create_nt(size):

result = ()

for index in range(size, 0, -1):

result = (index, result)

return result

#edef

# concatenates two nested tuples

def concat_nt(nt1, nt2):

if nt1 == ():

return nt2

else:

(head_single, tail_group) = nt1

return (head_single, concat_nt(tail_group, nt2))

#edef

def dummy(nt):

if nt == ():

return ()

else:

(head_single, tail_group) = nt

return dummy(tail_group)

#edef

class Timer(object):

def __init__(self, verbose=False):

self.verbose = verbose

def __enter__(self):

self.start = time.time()

return self

def __exit__(self, *args):

self.end = time.time()

self.secs = self.end - self.start

self.msecs = self.secs * 1000 # millisecs

if self.verbose:

print ('elapsed time: %f ms' % self.msecs)

#eclass

class Benchmark:

def __call__(self):

self.bench("dummy", dummy, create_nt(1000000))

self.bench("naive reverse 1k", naive_reverse_nt, create_nt(1000))

self.bench("naive reverse 10k", naive_reverse_nt, create_nt(10000))

self.bench("tailend reverse 100k", tailend_reverse_nt, create_nt(100000))

self.bench("tailend reverse 1M", tailend_reverse_nt, create_nt(1000000))

#edef

def bench(self, msg, call, arg):

with Timer() as t:

call(arg)

print("%s : %s s" % (msg, t.secs))

#edef

#eclass

sys.setrecursionlimit(1500000)

threading.stack_size(0xFFFFFFF)

t = threading.Thread(target=Benchmark())

t.start()

t.join()

-- Haskell Implementation of Reverse

import Text.Printf

import Control.Exception

import System.CPUTime

naive_reverse [] = []

naive_reverse (h:t) = (naive_reverse t) ++ [h]

tailend_reverse lst = tailend_reverse_aux [] lst

tailend_reverse_aux acc [] = acc

tailend_reverse_aux acc (h:t) = tailend_reverse_aux (h:acc) t

time :: IO t -> IO t

time fun = do

start <- getCPUTime

v <- fun

end <- getCPUTime

let diff = (fromIntegral (end - start)) / (10^12)

printf "%0.6f secs\n" (diff::Double)

return v

bench fun funName siz = do

printf "%s with %d: " (funName::[Char]) (siz::Int)

let list = [1..siz]

time $ fun list `seq` return ()

dummy [] = []

dummy (h:t) = dummy t

main = do

bench dummy "dummy" 10000000

bench naive_reverse "naive reverse 100k" 100000

bench naive_reverse "naive reverse 1M" 1000000

bench naive_reverse "naive reverse 10M" 10000000

bench tailend_reverse "tailend reverse 1M" 1000000

bench tailend_reverse "tailend reverse 10M" 10000000

% Picat Implementation of Reverse

naive_reverse([]) = [].

naive_reverse([H|T]) = naive_reverse(T) ++ [H].

tailend_reverse(List) = tailend_reverse_aux(List, []).

tailend_reverse_aux([], Acc) = Acc.

tailend_reverse_aux([H|T], Acc) = tailend_reverse_aux(T, [H|Acc]).

dummy([]) = [].

dummy([H|T]) = dummy(T).

% to benchmark type the following into the interpreter:

% _List=1..10000000, dummy(_List)=_RList

% _List=1..10000, time(naive_reverse(_List)=_RList)

% _List=1..100000, time(naive_reverse(_List)=_RList)

% _List=1..1000000, time(tailend_reverse(_List)=_RList)

% _List=1..10000000, time(tailend_reverse(_List)=_RList)

Miscellaneous:

This benchmark was done on a machine with the following specifications:
OS: Windows 10 Home (64-bit)
CPU: Intel i5-3317U
Ram: 6.00GB

The following interpreters/compilers were used for this benchmark:
Python 3.5.0 (32-bit)
Glasgow Haskell Interpreter 7.10.2 (32-bit)