So I had a brainwave the other day while out running. There is a particular type of application for generative music that I want to implement that involves leveraging a LAMP style stack in order to serve up a daily dose of music to the url mindfulmusic.today. I’ve got a bit of time on my hands at the moment, so I figure that I can structure a project and learn a bunch about some new technologies that I’ve been wanting to check out. The brainwave came after listening to a guided meditation by the zen master Henry Shukman who was relaying the following koan
Not Knowing is Most Intimate
Dizang asked Foyan, “Where are you going from here?”
Fayan said, “I’m on pilgrimage.”
“What sort of thing is pilgrimage?”
“I don’t know.”
“Not knowing is most intimate.”
Fayan suddenly had a great awakening.
Anyway, in light of the koan and upon pondering a way to approach the project that I had in mind, I figured it might be interesting to collect some of my approach together into a series of blog posts entitled not knowing… Basically, the whole idea with approaching it in this way is to try and develop a bit more of an understanding about some key technologies and practices that I’m interested in exploring. The idea of not knowing what I am doing is quite familiar as a composer, and also more recently as a software developer, so hopefully I will be able to illuminate my ignorance brightly.
I was messing around with a python exercise this morning on hackerrank which
required implementing a few simple data structures and classes. There was
nothing massively complicated about the exercise. The first part involved
implementing a Multiset class, which I did as follows:
class Multiset:
def __init__(self, values=[]):
self.values = values
def add(self, val):
# adds one occurrence of val to the multiset
self.values.append(val)
def remove(self, val):
# removes on occurrence of val from the multiset, if any
if val in self.values:
self.values.remove(val)
def __contains__(self, val):
# returns True when val is in the multiset, else return False
found = False # set initial result
self.values.sort()
for value in self.values: # search
if val == value:
found = True
break
return found
def __len__(self):
# returns number of elements in the multiset
length = len(self.values)
return length
Logically, this seems to cover it and the initial tests pass. As soon as there is a timeout limit set for the test suite though and we try to process a large set of numbers, we run into trouble. So I thought I’d look into it a bit and figure out some of the ways that I could improve the code speed. There are a couple of well worn adages about optimization such as the best is the enemy of the good (Voltaire) or premature optimization is the root of all evil (D. Knuth), so I have dutifully avoided attempting to optimize much in many of my programs up until now. That’s what makes it such a good candidate for the not knowing series!
So, intuitively it’s pretty easy to understand where some of the issues with
this problem are going to arise. We’re trying to create a class that handles a
large set of data. If we’re going to want to get anything reasonable done at
all, we’re going to want make sure that the data is sorted. The class is simple
enough, it just contains a simple list container and a bunch of methods.
The sort is really important for the contains function, but really we are going
to want to do the sorting before we even call that member function. Ideally the
list would be sorted when the object is initialized and when a new member is
added.
Oh yeah, by the way, you usually want to back up any intuitions with some sort of measurements that give you useful data. For this purpose, I discovered a couple of useful little python tools to use on our test program. I’m not going to go to the trouble of importing a unit test framework here, for our purposes it should be enough to simply mock up some data to try out the functions.
So where should we sort? Well, above I’m electing to sort in one place when we
call the Multiset.__contains__. Sort is an expensive operation, so we don’t
want to be calling it willy nilly, let’s just leave it where it is as a single
call before we cycle through the set to find the elements. We know from
complexity theory that an unsorted list runs in O (n) time, whereas sorted will
yield O (log n).
...
if __name__ == '__main__':
import main
# create a set of 10000 random values that remains stable while we test
testvals = []
random.seed(5)
for i in range(1000000):
testvals.append(random.randint(1, 10000))
# create a set of 10 random values to remove
rvals = []
random.seed(4)
for i in range(10):
rvals.append(random.randint(1, 10000))
# create a set of 100 values to search for
findvals = []
random.seed(3)
for i in range(100):
findvals.append(random.randint(1, 10000))
m = Multiset()
# see how long it takes to add 10000 numbers
for v in testvals:
m.add(v)
# see how long it takes to remove a subset of 10
for r in rvals:
m.remove(r)
# see how long it takes to find a subset of 100
result = []
for f in findvals:
result.append(f in m)
The processor in my laptop is snappy enough, so it handles sets with up to 1,000,000 elements pretty easily. As soon as we go 10x beyond this, things start to slow down dramatically. Okay, so there are a couple of useful tools to bring in at this point:
python -m cProfile hrtest.py
Gives us a profile output to the terminal that details what the various
function calls are costing us. cProfile allows us to save this output as a
file with the -o tag and by using the pyprof2calltree module, we can create
a format that can be viewed in KCacheGrind.
pip install pyprof2calltree
...
python -m cProfile -o hrtest.cprof hrtest.py
pyprof2calltree -k -i hrtest.cprof
Viewing this output, we can see that what’s costing us the most in term of
cycles are the calls to Multiset.__contains___
We want to improve the speed of this function, so let’s use the dis module to
dissasemble the bytecode and see how our modifications affect how the program
compiles. Also, let’s use timeit() to see exactly how long the code takes to
execute.
So the first improvement we can try is to use a generator. Generators are a functional programming technique, another thing I know very little about. After mucking about with haskell for an hour this morning, it’s perhaps enough to state for the moment, that the main difference between functional and procedural paradigms is that there is not as much state getting passed around in functional programming.
class MultisetFast:
#... same implementation as Multiset
def __contains__(self, val):
# returns True when val is in the multiset, else return False
self.values.sort()
for value in self.values: # search
if val == value:
yield True
This minor change to our function already gives a noticeable improvement, the actual compilation is unaffected, as evidenced by the disassembly listing, but the speed improves by 3x. The timing is how long it takes to run the contains function over a list of 100000 elements, asserting whether it contains one of 100 possible search items. I’m running the function 100 times, so averaging this means that we require 0.23 and 0.07 respectively to complete the operation.
time pre-optimized: 23.722660299012205
time optimized: 7.319715256002382
Another functional programming trick that we can implement here is to use a list comprehension.
resultm = []
def findvals(queryvals, mset):
for f in queryvals:
resultm.append(f in mset)
def findvalsfast(queryvals, mset):
resultmf = [i for i in queryvals if i in mset]
This causes the compiler to behave differently. And actually, there are no further timing improvements, it’s perhaps even a marginally slower than the standard findvals function where. The one improvement is that the code is more concise, so conceivably contains less room for error.
dis.dis(findvals)
100 0 SETUP_LOOP 26 (to 28)
2 LOAD_FAST 0 (queryvals)
4 GET_ITER
>> 6 FOR_ITER 18 (to 26)
8 STORE_FAST 2 (f)
101 10 LOAD_GLOBAL 0 (resultm)
12 LOAD_METHOD 1 (append)
14 LOAD_FAST 2 (f)
16 LOAD_FAST 1 (mset)
18 COMPARE_OP 6 (in)
20 CALL_METHOD 1
22 POP_TOP
24 JUMP_ABSOLUTE 6
>> 26 POP_BLOCK
>> 28 LOAD_CONST 0 (None)
30 RETURN_VALUE
dis.dis(findvalsfast)
104 0 LOAD_CLOSURE 0 (mset)
2 BUILD_TUPLE 1
4 LOAD_CONST 1 (<code object <listcomp> at 0x7f5f2ecfa150, file "hrtest1.py", line 104>)
6 LOAD_CONST 2 ('findvalsfast.<locals>.<listcomp>')
8 MAKE_FUNCTION 8
10 LOAD_FAST 0 (queryvals)
12 GET_ITER
14 CALL_FUNCTION 1
16 STORE_FAST 2 (resultmf)
18 LOAD_CONST 0 (None)
20 RETURN_VALUE
Disassembly of <code object <listcomp> at 0x7f5f2ecfa150, file "hrtest1.py", line 104>:
104 0 BUILD_LIST 0
2 LOAD_FAST 0 (.0)
>> 4 FOR_ITER 16 (to 22)
6 STORE_FAST 1 (i)
8 LOAD_FAST 1 (i)
10 LOAD_DEREF 0 (mset)
12 COMPARE_OP 6 (in)
14 POP_JUMP_IF_FALSE 4
16 LOAD_FAST 1 (i)
18 LIST_APPEND 2
20 JUMP_ABSOLUTE 4
>> 22 RETURN_VALUE
Just as a final little test, I’m going to increase the size of the sample space that we are searching for values. The reason for doing this is that some aspects of the O complexity may not be fully understood if the sample space is too small. By increasing the number of elements in the searchable list from 100,000 to 1,000,000 and running our test functions again, our improvements reflect a 10x speed up. Again, I don’t fully understand the reason for this, something about the size of the set and the type of algorithm used for sorting/searching does have an effect.
time pre-optimized: 7.531111125004827
time optimized: 0.7105367759941146
Okay, that’s it for now, what are the takeaways? Well, there are a couple of useful tools that we can use to examine our python code more closely and to see where the bottlenecks are happening, functional programming methods such as generators and list comprehensions can be leveraged to give us increases in speed and improve code readability.
Here’s the full code listing:
#!/bin/python3
import math
import os
import re
import sys
import random
class Multiset:
def __init__(self, values=[]):
self.values = values
def add(self, val):
# adds one occurrence of val to the multiset, if any
self.values.append(val)
def remove(self, val):
# removes on occurrence of val from the multiset
if val in self.values:
self.values.remove(val)
def __contains__(self, val):
# returns True when val is in the multiset, else return False
found = False # set initial result
self.values.sort()
for value in self.values: # search
if val == value:
found = True
break
return found
def __len__(self):
# returns number of elements in the multiset
length = len(self.values)
return length
class MultisetFast:
def __init__(self, values=[]):
self.values = values
def add(self, val):
# adds one occurrence of val to the multiset, if any
self.values.append(val)
def remove(self, val):
# removes on occurrence of val from the multiset
if val in self.values:
self.values.remove(val)
def __contains__(self, val):
# returns True when val is in the multiset, else return False
self.values.sort()
for value in self.values: # search
if val == value:
yield True
def __len__(self):
# returns number of elements in the multiset
length = len(self.values)
return length
if __name__ == '__main__':
# create a set of 10000 random values that remains stable while we test
testvals = []
random.seed(5)
for i in range(100000):
testvals.append(random.randint(1, 10000))
# create a set of 10 random values to remove
rvals = []
random.seed(4)
for i in range(10):
rvals.append(random.randint(1, 10000))
# create a set of 100 values to search for
queryvals = []
random.seed(3)
for i in range(100):
queryvals.append(random.randint(1, 10000))
m = Multiset()
mf = MultisetFast()
# see how long it takes to add 10000 numbers
for v in testvals:
m.add(v)
mf.add(v)
# see how long it takes to remove a subset of 10
for r in rvals:
m.remove(r)
# see how long it takes to find a subset of 100
resultm = []
def findvals(queryvals, mset):
for f in queryvals:
resultm.append(f in mset)
def findvalsfast(queryvals, mset):
resultmf = [i for i in queryvals if i in mset]
import dis
random.seed(2)
rint = random.randint(1, 10000)
print("dis.dis(findvals)")
dis.dis(findvals)
print("dis.dis(findvalsfast)")
dis.dis(findvalsfast)
# timeit stuff
import timeit
print("time pre-optimized: ", timeit.timeit(r"""import random
class Multiset:
def __init__(self, values=[]):
self.values = values
def add(self, val):
# adds one occurrence of val to the multiset, if any
self.values.append(val)
def remove(self, val):
# removes on occurrence of val from the multiset
if val in self.values:
self.values.remove(val)
def __contains__(self, val):
# returns True when val is in the multiset, else return False
found = False # set initial result
self.values.sort()
for value in self.values: # search
if val == value:
found = True
break
return found
def __len__(self):
# returns number of elements in the multiset
length = len(self.values)
return length
# create a set of 1000000 random values that remains stable while we test
testvals = []
random.seed(5)
for i in range(1000000):
testvals.append(random.randint(1, 10000))
# create a set of 100 values to search for
queryvals = []
random.seed(3)
for i in range(100):
queryvals.append(random.randint(1, 10000))
m = Multiset()
for v in testvals:
m.add(v)
# see how long it takes to find a subset of 100
resultm = []
for f in queryvals:
resultm.append(f in m)""", number=1))
# timeit stuff
print("time optimized: ", timeit.timeit(r"""
import random
import bisect
class MultisetFast:
def __init__(self, values=[]):
self.values = values
def add(self, val):
# adds one occurrence of val to the multiset, if any
self.values.append(val)
def remove(self, val):
# removes on occurrence of val from the multiset
if val in self.values:
self.values.remove(val)
def __contains__(self, val):
# returns True when val is in the multiset, else return False
values = sorted(self.values())
for value in self.values: # search
if val == value:
yield True
def __len__(self):
# returns number of elements in the multiset
length = len(self.values)
return length
# create a set of 1000000 random values that remains stable while we test
testvals = []
random.seed(5)
for i in range(1000000):
testvals.append(random.randint(1, 10000))
# create a set of 100 values to search for
queryvals = []
random.seed(3)
for i in range(100):
queryvals.append(random.randint(1, 10000))
mf = MultisetFast()
for v in testvals:
mf.add(v)
# see how long it takes to find a subset of 100
resultmf = [i for i in queryvals if i in mf]
""", number=1))