combinations performance

[asbisen]

while working with combinations() i noticed considerable performance difference between the runtime on python vs julia 0.5 and was wondering if I am doing something wrong?

runtime for walking over a subset of 3 items from a list for python 3.5 is 0.5022 seconds and similar code for julia takes 3 times more 1.55 seconds

Below is the sample code to reproduce the test

Python Code

import requests
import itertools
import time


def get_data(url):
  req = requests.get(url)
  lines = req.text.split("\n")
  return lines


def subsets(lst, num):
    for sub in itertools.combinations(lst, num):
        tmp=sub

if __name__ == "__main__":
    url = "https://raw.githubusercontent.com/spacefinity/sparespace/master/tools/city-list.txt"
    lst = get_data(url)

    st_time = time.clock()
    subsets(lst, 3)
    print("Elapsed time %2.4f seconds" % (time.clock()-st_time))

Elapsed time 0.5022 seconds

Julia Code

import Requests: get
import Combinatorics: combinations

function get_data(url)
  req = get(url)
  dat = readstring(IOBuffer(req.data))
  dat = split(dat, '\n')
end

function subsets(lst, num)
  for sub in combinations(lst, num)
    tmp=sub
  end
end

lst=get_data("https://raw.githubusercontent.com/spacefinity/sparespace/master/tools/city-list.txt");
@time subsets(lst, 3)

1.558682 seconds (56.66 M allocations: 2.814 GB, 15.34% gc time)

[KristofferC]

Virutally all time is spent on the following three lines:

Combinatorics.jl/src/combinations.jl

Line 15 in a748259

comb = [c.a[si] for si in s]

- collects an array = heap allocation

Combinatorics.jl/src/combinations.jl

Line 20 in a748259

s = copy(s)

- copy an array = heap allocation

Combinatorics.jl/src/combinations.jl

Line 31 in a748259

(comb,s)

- wraps heap allocated objects in a tuple = heap allocation

[asbisen]

Thanks @KristofferC. A new data point.

I just tried subsets() from Iterators.jl and it's slightly faster than combinations but still a lot slower than python.

# with Iterators.subsets()
1.164676 seconds (47.23 M allocations: 1.830 GB, 14.97% gc time)

# with Combinatorics.combinations()
1.597081 seconds (56.66 M allocations: 2.814 GB, 15.08% gc time)

[mschauer]

Closed by #73