Mostly High Performance

2015-02-16

Performance of Membership Tests

Some people think that performance in Python is inscrutable. But surely there is one thing we can all agree on... membership tests should be done on something hashed, like dictionaries or sets, not on a list.

Metrics: M values between 0 and N-1 are in a collection. How long does it take to test for each of N possibilities in turn? These values are the total search time divided by the number of searches, so they are an average time per single lookup.

Analysis

The list is, unsurprisingly, a couple of magnitudes worse than the set and dict. Note that the amount of time it takes to lookup a value in a list is linear with the number of elements. (The value of each increasing dot increases exponentially, so a constant distance between dots on a log graph implies linear growth.) This makes intuitive sense.

The time it takes to look up a value in a set or dict is suspiciously identical. In fact, they use the same algorithm and share some code. You can think of sets as dictionaries with an unused value.

Digression - Python implementation of dict

In Python a dict is a hash map. (Maps don't need to be hash mapped; they could be a binary tree like in C++.) Basically, the key is turned into an integer value by way of the hash function, __hash__. The hash value modulo the size of the hash indicates into which slot the key/value pair is inserted. Sometimes, multiple keys will hash to the same slot and "collide". When this happens, there are two solutions: open or closed addressing. With open addressing (such as for a Python dict) the next¹ slot is used. With closed addressing, each slot is a linked list of all entries which hash to that slot².
Clearly, open addressing cannot contain more key/value pairs than there are slots, so they will automatically resize when they get nearly full. There is a fairly severe performance degradation that happens when the hash begins to be about three quarters full; hashes typically resize at a given occupancy rate³.

Notes:

¹: ... for certain values of "next". Sometimes the next slot is the previous slot index plus one and progresses linearly, other times it progresses quadratically. Other times it may be based upon the hash (before the modulo). It may take into account how many times it has tried to find a slot. The exact algorithm doesn't matter just so long as it is repeatable and gets to a blank slot quickly.

²: Using a linked list is simpler than scanning ahead, but it has problems of its own. There can be serious performance degradation if the keys hash to the same slot (not just the same hash value, which would trip up open addressing as well). This makes the closed addressing solution particularly unsuitable where the keys may be chosen maliciously. Using something like a tree rather than a list would help, but not eliminate, the issue. Open addressing could also be susceptible to malicious keys, although such implementations must support dynamic resizing, which helps a bit (both in complicating the attack and automatically resolving one).

³: Like any resize operation, the complexity is probably O(n), but amortized to O(1). Some applications may need better time guarantees. It is possible to incrementally resize the hash. For instance, any addition could be added to the new, double-sized hash, while queries could check both hash locations. The hashing function is probably the most expensive operation, and that can be reused. The modulo would be done twice. Any query could also migrate the value to the new hash. (But the slot should still be marked as occupied, or else searching for collided values may fail). Any insert should be accompanied with a migration of an old value. That way, it is guaranteed that the old hash has been completely migrated by the time the new (double-sized) hash has filled up.

Graph Analysis

On the first graph the X axis represents N, which is the max potential value in the collection. Darker colors represent more actual entries in the collection. The downwards slope to the right indicates that for a given collection size, a set/dict will get more efficient the more times it is queried. Another possibility is that the collection gets more efficient the sparser the data that it contains, but this seems unlikely. Why would a collection containing 10,20,30 be more efficient than one containing 100,200,300? The most inefficient query is the one where the collection is fully populated. Sets/Dicts use hashing. Hashes usually work by using a function called "the hash function" to turn the contents into a numeric key. This key is used to find a position in an array. In the case of collisions, the next position is checked to determine if the key is located there. When the collection gets full it takes longer to see if the key is present.

The next graph shows something different: The shading and the X axis have been swapped, so that the X axis represents the number of items in the collection, while the shade represents the maximum value that is present.

The time to test membership in lists seem to be entirely dependent upon the length of the list. This makes sense if the collection is generally sparsely populated, and it must generally search the whole list before confirming that the item is not there. (Even if it is not there, the complexity is O(n), so it is still linear.)

Perhaps less obvious is that dictionaries and sets perform best, and identically, until the time that they near full population in the collection. I.e., if the dict/set has X members, the numbers that are contained are between 0 and X. Presumably this is the effect of hash slot collision... the tight clustering of values may be causing more has collisions.

Also, the time to find an object in a dictionary is fairly constant, but it does appear to be rising slowly as the number of entries in the dictionary is increased.

If the hash function is complex relative to the comparison function, and if the most likely values to be searched for are located earliest in the list, then it may make sense to use a list instead of a dict. Frankly, however, I think the graph above really demonstrates how extreme the situation must be for this to be true. It was generated with 0.9 probability, so that it was 90% likely that the first item is the one requested. Failing that, it is 90% likely to ask for the second item, and so on. That is a pretty extreme case. Hooray for efficient dicts and sets!

2015-02-09

Setting up clamav antivirus on Ubuntu

Installing Anti-virus on Ubuntu

My wife's been using a Linux box in the kitchen as her primary web browsing computer. It also hosts my version control servers that back up everything that matters in the world. I figured that it was time I installed some anti-virus on it. Clamav seemed to be the simplest/best option.

The only hitch is that I don't get to sit at the computer much. Mostly I SSH in from the bus, but I do that infrequently. I can crontab the scan, but I really need the results pushed to me. For another program I've written a module that will send an email using a secondary gmail account, so I just needed to hook clamav up to it.

cp_email.py

cp_email.py takes command line parameters to indicate how to send the email, and then runs a command and sends the results. This was easier than setting up email on the Linux box so that it could send email natively. Cron can email the results, but I didn't want to hook that up. This way I can add wrapping code to do arbitrary post-processing (filters, summarizing). It is also more easily portable.

I was rather concerned with security. It would be foolish to include a plaintext password on the command line, as that can be seen by all processes running on the machine. The --ob will perform a trivial de-obfuscation on the password. Each character will be converted into the preceding ascii value. If the password is "cat", the obfuscated password (that should be given to cp_email) is "dbu". This obviously cannot stop a mildly determined attacker. The preferred method of specifying a password is by reference to a text file. A password preceded by an at sign ("@") is taken to be a filename. The file is loaded. If there are multiple lines in the file then the password is the taken from the last line in the file. This method can also be used to specify the username, where the first line of a multi-line file is taken. This allows the username and password to specified in the same file, which should, of course, be read protected from the world. Only the user should be able to read it. It should also be ignored by version control so that it is not available to all those who can access the source. @ and --ob can be used together for a small extra measure of security.

crontab -e

Here is my crontab entry:

0 4 * * * (rm /tmp/scan ; ((clamscan -i -l /tmp/scan -z --exclude-dir="^/(dev|cdrom|media/cdrom|sys)" -r /)) ; chmod a+r /tmp/scan ; ( cd /home/myusr/dir_with_password ; su -c "python /home/myusr/lib/cp_email.py --ob run-and-send @password @password recipient@email.com cat /tmp/scan --subject='Antivirus'" myusr))

I could have executed clamav directly from the cp_email script. However, clamav needs to run as root to be able to see all the files to scan and I didn't want root to be running a program which is held in version control and might change. If I did want to run it that way, then this would be the appropriate crontab entry:

0 4 * * * ( cd /home/usrofsvn/markets/Code/irrigate ; python ../lib/cp_email.py --ob run-and-send @password @password recipient@email.com clamscan -r / --subject="Antivirus run")

cp_email.py --help

usage: cp_email.py run-and-send [-h]
                                [--loglevel {CRITICAL,ERROR,WARNING,INFO,DEBUG}]
                                [--ob] [--subject SUBJECT]
                                username password recipients args [args ...]

positional arguments:
username              The username to use to log into gmail. The username must
be an @gmail.com address. If preceded by @, then
                        the value indicates a filename. The first line of the
                        file contents will be used for the username.
password              The password, or, if preceded by @, the filename where
                        the password is stored. If the file contains multiple
                        lines, it will take the password from the last line.
recipients            Comma separated list of emails to receive email.
                        (Specify "-" for the sending username.)
args                  The remaining arguments are the command to run.

optional arguments:
-h, --help            show this help message and exit
--loglevel {CRITICAL,ERROR,WARNING,INFO,DEBUG}
                        (default: INFO)
--ob                  Enable elementary password obfuscation (ROT1)
--subject SUBJECT     The subject for the email.

2012-10-11

My Development Tools

Whether developing on my desktop or laptop, Linux or Windows, my tools of choice are pretty bare-bones. I edit my files in vim and I incrementally develop my program by using my "kr" script. "kr" looks for changes in whatever files you give it, and then reruns a command when it detects a change. I.e.:

> kr *.py -c 'tests.py'

Would look for a change in any .py file and rerun the "tests.py" script.

> kr *.c *.h makefile -c 'make ; application param1 param2'

Would look for a change in any .c/.h file, or the makefile, and when a change is detected it remakes and runs "application" with the two params "param1" and "param2".

Developing is easy, just save the file I'm editing and look in the other window to see what happens with the new code. Usually I use this for re-running a python program, which I develop a bit at a time. I fix an error, save, and quickly see the next error. It works best, of course, when the file is able to run quickly.

I've also used it to check for a data file change, at which point it regenerates an image. In another window a separate "kr" script looks for a change in the image file, and runs a program to render it. (The two "kr" scripts had to run on different machines, or else they could have been combined.)

Find the current version here.



#Copyright 2012 Mark Santesson
#
#   Licensed under the Apache License, Version 2.0 (the "License");
#   you may not use this file except in compliance with the License.
#   You may obtain a copy of the License at
#
#       http://www.apache.org/licenses/LICENSE-2.0
#
#   Unless required by applicable law or agreed to in writing, software
#   distributed under the License is distributed on an "AS IS" BASIS,
#   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
#   See the License for the specific language governing permissions and
#   limitations under the License.

import sys
import time
import re
import stat
import os
import glob
import operator
import optparse


if __name__ == "__main__":

    parser = optparse.OptionParser (
                        usage = '%prog -c  files ...',
                        description = 'Repeatedly run a command whenever any one of a list of files changes.')
    parser.add_option('-c', '--command', dest='command', type="string",
            help='Specify command to run when a change is detected')
    options, args = parser.parse_args()

#    print "Found args: " + repr(args)
#    print "Found command: " + repr(options.command)

    if not args:
        print '\n' + os.path.basename( sys.argv[0] ) + ' requires some files to monitor.'
        sys.exit(1)

    if not options.command:
        print '\nError: A command to run is required.'
        sys.exit(1)


    file_times = dict()
    globbed = sum( [ glob.glob(x) for x in args ], [] )
    for x in globbed:
        file_times[x] = 0.0

    print file_times

    while True:
        rerun = False

        for f in file_times.keys():
            attempts_left = 5
            t = None
            while attempts_left and t == None:
                try:
                    t = os.stat(f)[ stat.ST_MTIME ]
                except WindowsError, e:
                    time.sleep(0.1)
                    attempts_left -= 1

            if t > file_times[f]:
                rerun = True
                file_times[f] = t

        if rerun:
            print time.strftime('\n\n--- Rerunning at %H:%M:%S :') + repr(options.command)
            ret = os.system( options.command )

            if ret:
                print '\n\n--- ERRORED %r' % (ret,) + time.strftime(' at %H:%M:%S.')

            else:
                print time.strftime('\n\n--- Done at %H:%M:%S.')

        else:
            time.sleep(0.5)

else:
    raise Exception( 'This module is not meant to be imported.' )

My Development Tools by Mark Santesson is licensed under a Creative Commons Attribution 3.0 Unported License.

2012-09-04

Detecting Loops in Linked Lists

<br /> Detecting Loops in Linked Lists<br />

I was interviewing at a company and one of the questions was how to detect loops in a linked list.

A linked list is where there are a bunch of objects... perhaps bits of memory that have been allocated... and each one points to the next one in the list. Usually, the last one points to NULL. Sometimes the last one points to the "first" one. But then, in such a list, what does "first" really mean? (Perhaps how you refer to the list as a whole.)

Sometimes you may have a non-circular list where the last element points to an item elsewhere in the list, rather than NULL. Or perhaps you think you have a circular list but the last element does point to NULL. That would be an error. You'd like to be able to detect it... and quickly. To do this, you need to be able to determine if a list has a loop, but you can't just scan through it looking for NULL or the start value, because the "last" item might not point to the "first"; the last node could point to the node just before it. Or the one before that...

This is the sort of thing I probably saw in college but didn't remember. On the spot, I came up with the following algorithm:

Jumping by Powers of Two Algorithm


 bool DoesListLoop( Node const * cur )
 {
  Node const * base = cur;
  int jump = 1;
  int remain = 1;
  while (cur) 
  {
   cur = cur->next;
   if (cur == base) return true;
   if (! --remain)
   {
    jump *= 2;
    remain = jump;
    base = cur;
   }
  }
  return false;
 }

In short, this will race a pointer along the list and every time it has traversed a number of nodes equal to a power of two it resets the base pointer to the current pointer. Each time it moves the "current" pointer ahead it compares it to the base pointer. A match indicates a loop. Finding a NULL means it ended and there is no loop.

More fundamentally, any solution to this problem must advance a pointer through the list forever. If the end of the list is found then there is no loop. If it loops then you will never reach the end, but in order to discern this from an arbitrarily long list you need to match one node with another node previously seen. In order to match loops that loop back to a point arbitrarily far into the list you need to look arbitrarily far ahead of the start, but also arbitrarily far behind the node you are checking in the front. You need to let the "cur" pointer get farther and farther from both what you are comparing against and the start of the list. I did this by resetting the "base" pointer at larger and larger intervals.

Back at the interview, they asked me "do you mean, that you have two pointers, and you advance one pointer two steps for every one step that you advance the other pointer?"

"That sounds like it would work, but, no, I don't mean that." I explained my idea in more detail. They said they thought that it would work, but they wanted to talk about their version some more. Presumably they thought it was a better algorithm (but perhaps they just thought it was simpler and made for a better interview discussion). I think they were wrong. As I've since learned, they meant Floyd's Cycle-Finding Algorithm, published in 1967, also known as "The Tortoise and the Hare Algorithm":

"Two Steps for the Forward Pointer, One Step for the Back Pointer"


 bool DoesListLoop( Node const * cur )
 {
  Node const * base = cur;
  if (!cur) return false;
  while (true)
  {
   cur = cur->next;
   if ( ! cur ) return false;
   if ( base == cur ) return true;

   cur = cur->next;
   if ( ! cur ) return false;
   if ( base == cur ) return true;

   base = base->next;
  }
 }

How do we measure performance?

As far as performance is concerned, we want to minimize the time (or number of operations) required to determine whether a list is looping or not. We might want to optimize for the non-looping case since that is probably the most likely case (if loops are errors), and we'd like to be able to identify those quickly. We also may have short or long lists, the looping part might be shorter or longer, and the size of the nodes might vary.

This graph shows the number of operations to solve the various cases. Here I take an operation to be a memory fetch to look at the next node. I don't count branching as a cost. (Branch prediction should work very well in this case.) This certainly isn't a perfect estimate, but it does capture what I think proves to be the major cost.

Theoretical cost of the two algorithms. The "Half-Speed" algorithm is in green. My "Jumping by Powers of Two" algorithm is in red. The Y axis counts "operations" to solve the problem. An operation is a memory fetch. The X axis is the number of elements in the list. Lighter shades indicate lists where the loop goes back closer to the beginning of the list. Darker shades indicate looping more towards the end of the list. The single lightest shade indicates no loop. The blue points indicate the benefit of the jumping algorithm over the half-speed algorithm.

Theoretical cost of the two algorithms, as above, but with a log-log scale and without the blue difference points.

From this simulation we can see that the jumping algorithm is always as good or better than the half-speed algorithm. Although, it should be restated that this is just a simulation of the memory fetching cost. For small lists that can fit entirely into local cache, the cost is only 2/3 of this for the half-speed case. In that case, you would have some cases where using the half-speed was better.

Lighter shades (looping goes back closer to the beginning) generally appear to be harder to solve.

Also note that the performance of the two algorithms don't diverge... they always stay pretty close, at least on a log scale. This confirms that they are of the same order, O(n).

It is nice to see that the theory confirms our expectations, but models are no proof of reality, so let's move on to actual recorded metrics.

Demonstrated Performance

I've implemented the algorithms in C++ and timed them on a Linux desktop using low-end hardware with a vintage around 2010.

Actual performance. Red is my "jumping" algorithm, green is the half speed algorith. X axis is the number of nodes in the list. Color indicates where the list loops back to... lighter colors loop back closer to the beginning, but the lightest color does not loop.

The difference between the two algorithms. Positive numbers reflect an advantage to my jumping algorithm.

These results track well with the theoretical results (note the log-log graph). It appears to be more or less a wash until the size reaches well over a million and then (when it no longer fits in cache?) the jumping algorithm takes off.

Here's a graph of the algorithms when looking only at a non-looping list.

Performance with different sizes of nodes. Theoretically, cache effects might be exposed at earlier list sizes. The differences are not terribly obvious, althoguh jumping still seems to perform better than half-speed.

The difference between the two algorithms. Positive numbers reflect an advantage to my jumping algorithm. There doesn't seem to be much pattern to the distribution of node size (shade).

Finally, here's the most important graph. Relative performance for verifying a non-looping list, as a function of size of the list. As this would normally by the typical use case, this is therefore the most important graph. If a list did loop, then we wouldn't be as concerned about the performance since we're probably about to report an error and stop the program.

Performance of verifying that a list does not loop.

The difference between the two algorithms for non-looping lists. The scale is percentage of the half-speed algorithm's time to completion. The value indicates how much less time the jumping case took.

As it turns out, the jumping algorithm isn't really much better than the half-speed algorithm in my theoretically most differentiating test case. From the difference graph it appears that the benefit does continue increasing as the length of the list increases. This indicates that the benefit is not kicking in for a while, presumably because of cache.

Theoretically, not traversing the list twice should yield significant benefits once the memory that is used exceeeds the cache size. (Branch prediction would work very well in this case, but it still needs to get the memory in before it can fetch the next memory location.) This seems to be what we are seeing.

Parting Thoughts

If there are n elements in the list, both of these algorithms will terminate before running through about 2n nodes. They are both O(n). Can we do better? While we certainly can't improve on O(n), perhaps we can run through fewer nodes.

Ideally we'd be able to quickly check if we'd ever seen a node before, and therefore terminate after n nodes when we either find the end or find a node which we've seen before. However, the naive implementation would have us checking each node against each node we've already seen, which makes the algorithm O(n²).

Theoretically, a hash map would let us find whether we'd already seen a point in constant time, but the hash adds and lookups would probably take longer than the 2x multiple that we're trying to remove.

I think this is the best that can be done, excepting, of course, if you can mark flags to indicate if a node has been visited before. The is a page linked to below that has details on this method.

A silly digression in which an O(1) algorithm is presented

Interestingly, there is an algorithm technically qualifying as O(1) that works on modern computers. Specifically, you can race a pointer along in memory counting how many nodes you've seen. If the count reaches a number higher than you can fit in the memory available, then you must have a loop. This is worst-case O(1) because the number of operations is constant with respect to the list size... it only varies with the size of memory that is available to contain the nodes in the list, which is presumably constant. But if you consider the typical size of linked lists in comparison to even a 32-bit memory address, you can quickly see that this is also about the most inefficient algorithm imaginable. And therefore we have an O(1) algorithm which is probably the least efficient algorithm. Of course, it all depends on what your independent variable "n" represents. If it represents the number of nodes in your list, then this is O(1) (since the number of operations is constant, the memory size, regardless of how large the list is). If it represents memory size, or maximum possible nodes, then this is O(n), and probably much less efficient than the other algorithms listed. Always use an "n" which is meaningful for the analysis.

Hypothetical Case

Performance often depends upon the use case. For instance, if we are usually dealing with a non-looping list and just want to verify that quickly, then a better algorithm might be to track the expected length of the list and just race to the end. If it hasn't ended, then a more exhaustive search could be done. Or, if it is expected to loop, and always to the beginning (circular linked list), then the search can optimize for that.

Suppose there is a prioritized queue of elements. The elements are allocated as a std::vector because changing the size is infrequent and the number only ever grows. The elements refer to each other through offsets. The order rearranges as the priority of the various items shift around. For whatever reason, we want to be sure that the list terminates and doesn't loop. (Perhaps we are implementing the priority queue for Dijkstra's algorithm.) What is the most efficient way to do this? I suspect that the answer is in the previous (silly) section.