Can't find SymPy with iPython / iPython Notebook on Mac 10.8.2 (Mountain Lion)

SymPy allows you to see mathematical formulas in their hand written representation. It is just not easy to install on the Mac, at least on the Mountain Lion. It has to do with the package location for SymPy. Python finds the package, but not iPython and of course the notebook. So after installing SymPy, trying to import the module will fail like this:

ImportError: No module named sympy

However, inside the python prompt, I could import SymPy. And checking on the package path, showed where python was looking for, to find SymPy:

>>> import sympy
>>> print sympy.__file__
/opt/local/Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/site-packages/sympy/__init__.pyc

When I checked the module search path inside iPython, the list was shorter and the /opt/local path was not there :

In [7]: IPython.utils.module_paths.find_module("sympy")

In [8]:

In [10]: sys.path
Out[10]: 
['',
 '/usr/local/bin',
 '/Library/Python/2.7/site-packages/ipython-1.1.0-py2.7.egg',
 '/Library/Python/2.7/site-packages/readline-6.2.4.1-py2.7-macosx-10.7-intel.egg',
 '/Library/Python/2.7/site-packages/pyzmq-14.0.0-py2.7-macosx-10.6-intel.egg',
 '/Library/Python/2.7/site-packages/Jinja2-2.7.1-py2.7.egg',
 '/Library/Python/2.7/site-packages/MarkupSafe-0.18-py2.7-macosx-10.8-intel.egg',
 '/Library/Python/2.7/site-packages/tornado-3.1.1-py2.7.egg',
 '/Library/Python/2.7/site-packages/matplotlib-1.3.1-py2.7-macosx-10.8-intel.egg',
 '/Library/Python/2.7/site-packages/nose-1.3.0-py2.7.egg',
 '/Library/Python/2.7/site-packages/pyparsing-2.0.1-py2.7.egg',
 '/Library/Python/2.7/site-packages/scikit_learn-0.14.1-py2.7-macosx-10.8-intel.egg',
 '/Library/Python/2.7/site-packages/scipy-0.13.0-py2.7-macosx-10.8-intel.egg',
 '/Library/Python/2.7/site-packages/demjson-1.6-py2.7.egg',
 '/System/Library/Frameworks/Python.framework/Versions/2.7/lib/python27.zip',
 '/System/Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7',
 '/System/Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/plat-darwin',
 '/System/Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/plat-mac',
 '/System/Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/plat-mac/lib-scriptpackages',
 '/System/Library/Frameworks/Python.framework/Versions/2.7/Extras/lib/python',
 '/System/Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/lib-tk',
 '/System/Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/lib-old',
 '/System/Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/lib-dynload',
 '/System/Library/Frameworks/Python.framework/Versions/2.7/Extras/lib/python/PyObjC',
 '/Library/Python/2.7/site-packages',
 '/Library/Python/2.7/site-packages/ipython-1.1.0-py2.7.egg/IPython/extensions']

In [11]:

So I copied the package over to /Library/Python/2.7/site-packages/sympy so that iPython could find it:

sudo cp -R /opt/local/Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/site-packages/sympy /Library/Python/2.7/site-packages/

In [13]: IPython.utils.module_paths.find_module("sympy")
Out[13]: '/Library/Python/2.7/site-packages/sympy'

In [14]: from IPython.display import display

In [15]: from sympy.interactive import printing

In [16]: printing.init_printing()

In [18]: from __future__ import division

In [19]: import sympy as sym

In [20]: from sympy import *

In [22]: x, y, z = symbols("x y z")

In [23]: Rational(3,2)*pi + exp(I*x) / (x**2 + y)
Out[23]: 
        ⅈ⋅x 
3⋅π    ℯ    
─── + ──────
 2     2    
      x  + y

HTTP Request : Host header must be lower cased

In theory, the case of values specified in most HTTP Request headers is insignificant. But there are servers that do look for a specifically lower case Host header. These servers will return incorrect results if the case was different.

If you're building your own HTTP requests, and want to get back data that a typical browser would get, it would be a good idea to lower case the Host header before sending it to the server.

A case in point is http://www.BestBuys.com

Try to fetch the page with curl, like this : curl http://www.BestBuys.com

You do get a page, but look at it closely, it is an error page.

    <h1>PPI Exception (PDOException)</h1>
    <div><strong>File:</strong> /data/www_bestbuys_com/releases/20131017195710/PPI/Vendor/Doctrine/Doctrine/DBAL/Driver/PDOConnection.php</div>
    <div><strong>Line:</strong> 36</div>
    <div><strong>Message:</strong> SQLSTATE[HY000] [2002] No such file or directory</div>

Do this with wireshark running and observe the Host header :

Host: www.BestBuys.com\r\n

Now use curl, but specify a lowercased Host header :

curl -H "Host: www.bestbuys.com" http://www.BestBuys.com

Then you get the correct page. Browsers, understanding the imperfect implementations of web servers out there always lower case the Host. You can check this with wireshark. Try to get the page using any modern browser and look at the Host header in wireshark.

Here is another example of where the practical approach is not used in a very common library used to fetch web pages.

Java : remove specified characters from a string (and quickly!)

Recently, I had to remove extraneous carriage returns and line feeds from URLs on a path that had real-time performance concerns. There was already some code that did this job, albeit inefficiently :

    public static String remove(final String string,
                                final char remove)
    {
        if (string == null) throw new IllegalArgumentException("string is null");

        int index = 0;
        final StringBuilder stringBuilder = new StringBuilder(string);
        while ((index = indexOf(stringBuilder, remove, index)) != -1) {
            stringBuilder.deleteCharAt(index);
        }
        return stringBuilder.toString();
    }

This code, is inefficient as it forces the StringBuilder.deleteCharAt to shift all characters in the buffer left, each time a character that need to be removed is found. Here is how StringBuilder.deleteCharAt is implemented :

764 public AbstractStringBuilder deleteCharAt(int index) {
765         if ((index < 0) || (index >= count))
766             throw new StringIndexOutOfBoundsException(index);
767         System.arraycopy(value, index+1, value, index, count-index-1);
768         count--;
769         return this;
770     } 

So I searched around for a hopefully more efficient implementation of this basic function. There was a StringUtils (apache commons lang) function that looked hopeful. However, it was not really meant to remove characters from a string, but to replace them: StringUtils.replaceChars(String str, String searchChars, String replaceChars) Here is how that looks like:

public static String replaceChars(String str, String searchChars, String replaceChars) {
4168        if (isEmpty(str) || isEmpty(searchChars)) {
4169            return str;
4170        }
4171        if (replaceChars == null) {
4172            replaceChars = EMPTY;
4173        }
4174        boolean modified = false;
4175        int replaceCharsLength = replaceChars.length();
4176        int strLength = str.length();
4177        StrBuilder buf = new StrBuilder(strLength);
4178        for (int i = 0; i < strLength; i++) {
4179            char ch = str.charAt(i);
4180            int index = searchChars.indexOf(ch);
4181            if (index >= 0) {
4182                modified = true;
4183                if (index < replaceCharsLength) {
4184                    buf.append(replaceChars.charAt(index));
4185                }
4186            } else {
4187                buf.append(ch);
4188            }
4189        }
4190        if (modified) {
4191            return buf.toString();
4192        }
4193        return str;
4194    }

The code does not optimize for the case where the resulting string would be shorter than the original, so this code is likely to be slow. Next, I found a Guava function in com.google.common.base.CharMatcher : String removeFrom(CharSequence sequence). That used quite an interesting algorithm as follows:

  public String removeFrom(CharSequence sequence) {
    String string = sequence.toString();
    int pos = indexIn(string);
    if (pos == -1) {
      return string;
    }

    char[] chars = string.toCharArray();
    int spread = 1;

    // This unusual loop comes from extensive benchmarking                                                                                
    OUT: while (true) {
      pos++;
      while (true) {
        if (pos == chars.length) {
          break OUT;
        }
        if (matches(chars[pos])) {
          break;
        }
        chars[pos - spread] = chars[pos];
        pos++;
      }
      spread++;
    }
    return new String(chars, 0, pos - spread);
  }

It keeps track of the distance between the source and destination in the "spread" variable. However, this means that for each left shift, it needs to do a subtraction. Since these all seemed less than optimal, I decided to code my own. This was my first function, where I try to keep track of the first index for the destination.

    public static String remove2(final String string, final char... chars) {
        char[] arr = string.toCharArray();
        int dst = -1;
        for (int src=0; src<arr.length; src++) {
            boolean rm = false;
            for (char c : chars) {
                if (c == arr[src]) {
                    rm = true;
                    if (dst == -1)
                        dst = src; //set first dst pos 
                }
            }
            if (!rm && dst != -1) {
                arr[dst++] = arr[src];
            }
        }
        return dst == -1 ? string : new String(arr, 0, dst);
    }

Upon a hunch that the JVM should be smart enough to not copy a value from an address to itsef, I then decided to remove the check for the first destination index. Here is that version:

   public static String remove3(final String string, final char... chars) {
        char[] arr = string.toCharArray();
        int dst=0;
        for (int src=0; src<arr.length; src++) {
            boolean rm = false;
            for (char c : chars) {
                if (c == arr[src]) {
                    rm = true;
                }
            }
            if (!rm) {
                arr[dst++] = arr[src];
            }
        }
        return dst == string.length() ? string : new String(arr, 0, dst);
    }

Next I benchmarked the different functions with a simple test, using just one input. Depending on input, your results may vary, so it best to work with inputs you are likely to see in your scenario.

remove : 20.092s
Guava : 25.164s
apache commons langs : 1m33.573s
remove2 : 19.272s
remove3 : 12.109s

So for this simple test, Guava was worse than our hand-optimized remove3(). The apache common langs function took a big hit as it was not optimizing for removal. I'm curious why the Googlers went with their approach on Guava. It may be that all JVMs are not as smart as to prevent a dumb copy from the same address to itself, and Guava makes sure such code does not have a chance to get to the JVM, since the variable "spread" always being greater than 0, this assignment can never be from one address to itself :

chars[pos - spread] = chars[pos];

Java: splitting on a single character

If you want to split a Java String on a single character, on a compute intensive path in your code, you might want to stay clear of String.split. The JDK function uses a regular expression for splitting and before JDK 1.7, the String.split had no optimization for single characters.

An optimization was introduced in JDK 1.7, but if your split character happens to have special meaning in a regular expression (ex: ^ |), then the optimization will not apply.

I used org.apache.commons.lang.StringUtils.split to gain a roughly 3X advantage over the split call used in our servers.

Here is the performance test:

import org.apache.commons.lang.StringUtils;

public class TSplit {

    public static void main(String[] args) {
        if (args.length==0) {
            System.err.println("TSplit jdk|nojdk");
            System.exit(-1);
        }
        String var = "here|is|a|string|that|must|be|split";
        if (args[0].compareTo("jdk")==0) {
            for (int i=0;i<10000000;i++) {
                String[] splits = var.split("\\|");
            }
        } else {
            for (int i=0;i<10000000;i++) {
                String[] splits = StringUtils.split(var, '|');
            }
        }
    }
    
}

The results from the test :

[~/] time java -cp `echo /path/to/jars/*.jar|tr ' ' :` TSplit jdk

real 0m16.027s
user 0m16.245s
sys 0m0.412s
[~/] time java -cp `echo /path/to/jars/*.jar|tr ' ' :` TSplit nojdk

real 0m5.354s
user 0m5.395s
sys 0m0.304s
[~/] 

As this post shows, Users who encountered these problems pre-1.7 have sometimes hacked their code to even pre-compile the single split character to a regular expression. This unfortunately means, that if and when they upgrade to 1.7, the optimization that Sun added will have no effect.

Simulate a mysql connection error

In testing, we have to often simulate errors. How can we simulate a mysql connection error on a typical network that can be found in a corporate environment? Most times, the servers themselves are some place we have no physical access to and, what is more of a problem, shared by others. So we can't shut down the server, or unplug the cable.

There is a way we can simulate a mysql connection error using the swiss army knife of the hacker - netcat. netcat allows us to forward traffic coming to a particular port, to another one of our choosing. When we set up netcat this way, it starts listening on a port, and forwards all traffic received on this port to the other port.

Here is an example :

ncat -l 10.2.2.47 8080 --sh-exec "ncat 10.2.2.47 3306" 

This command will have netcat start listening on port 8080, you don't have to use port 8080, you can use any unused port on the machine. Then it forwards all traffic to port 8080 to port 3306. Now port 3306 is where mysql listens on. On the machine I ran this, the idea was to route all traffic to port 8080 to mysql on the same box. Now all you have to do is to change the connection string of your application being tested, to speak to port 8080 (instead of the default mysql port, 3306). Once you do that, port forwarding will still make the mysql calls work seamlessly. But now, when you want to simulate a mysql connection error, simply kill the ncat that is listening on port 8080. When you want to bring mysql back up, simply issue the ncat command again.

Here is how you'd use the mysql client to go via 8080:

mysql -uuser -ppass -h 10.2.2.47 --port 8080

(Make sure the host is specified as the IP. Specifying localhost will ignore the port and start using a socket file for communication.)

Voila, now you have a fairly painless way of simulating mysql errors. Of course the same technique can be used to simulate any errors generated by network calls where a server listens on a known port, which is all socket based applications.

Hadoop : Output of Combiner can be processed again by the Combiner

A combiner can be used in a map/reduce program to aggregate values locally at the mapper, before a call is made to the reducer. When a combiner is available, the output of the map() function is fed to the combine() function first. And the general understanding is that the output of the combine() function is sent over to the reduce() function on a reducer machine.

Except, it is not strictly correct. The output of combine() can be fed back into the combine() function for repeated aggregation. In general, this does not cause a problem, but one can write incorrect code, if one was not aware of this detail. An example would be a simple counting program.

This program counts the terms present in the given documents. In the reducer, the sum is incremented by 1 for each element in [c1, c2, ...] because, we know that all counts in this array are "1"s. That is because, the mapper always emits "1"s.

class Mapper
   method Map(docid id, doc d)
      for all term t in doc d do
         Emit(term t, count 1)

class Reducer
   method Reduce(term t, counts [c1, c2,...])
      sum = 0
      for all count c in [c1, c2,...] do
          sum = sum + 1
      Emit(term t, count sum)

Now let's add a combiner to aggregate the terms locally.

class Combiner
   method Combine(term t, [c1, c2,...])
      sum = 0
      for all count c in [c1, c2,...] do
          sum = sum + 1
      Emit(term t, count sum)

It is identical to the reducer. The sum is incremented by 1 for each "1" element in the array. But now, we see that we must change the reducer to not sum "1"s, as the combiner would be doing an aggregation first. So we change the reducer to this:

class Reducer
   method Reduce(term t, counts [c1, c2,...])
      sum = 0
      for all count c in [c1, c2,...] do
          sum = sum + c
      Emit(term t, count sum)

The thinking is that the array input into the combiner could never have values other than "1"s. But this is an incorrect assumption because, as we said, the output of a combiner, that would have produced aggregated values, other than "1"s, can be again input to the combine() function. Thus the correct combine() is as follows:

class Combiner
   method Combine(term t, [c1, c2,...])
      sum = 0
      for all count c in [c1, c2,...] do
          sum = sum + c
      Emit(term t, count sum)

In fact, this is identical to the reduce() function.

We can peek under the hood in Hadoop source code to see where this two step combining happens. Inside java.org.apache.hadoop.mapred.MapTask, a flush() method has two function calls of relevance.

sortAndSpill()
mergeParts()

sortAndSpill() is actually called early on by a spill thread as well. The flush() makes sure that any remaining data is properly spilled. flush() then interrupts the spill thread, waits for it to end, and then calls mergeParts().

sortAndSpill() is the section of code that runs as the mapper is writing the intermediate values into spill files. 

Inside sortAndSpill() :

            if (spstart != spindex) {
                combineCollector.setWriter(writer);
                RawKeyValueIterator kvIter =
                  new MRResultIterator(spstart, spindex);
                combinerRunner.combine(kvIter, combineCollector);
              }

This is where the combine() function is called first. But when data volume is high, Hadoop is unable to wait for all output from the mappers, before spilling the data to disk. When a threshold is reached, the buffers are spilled into a spill file. So it is quite possible, that one key gets spilled into two spill files. And if this happens, Hadoop can do yet another aggregation on running the data in spill files through the combiner. And that is partly what the mergeParts() function does:

         if (combinerRunner == null || numSpills < minSpillsForCombine) {
            Merger.writeFile(kvIter, writer, reporter, job);
          } else {
            combineCollector.setWriter(writer);
            combinerRunner.combine(kvIter, combineCollector);
          }

This is how combine() can be called twice, or more times, for the same key. So even if the mapper always emits a "1", the combiner could get values much larger than "1". It is always good practice to not assume the values coming into the combiner based on what is output from map().

Simulate Out Of Disk condition for a test (Linux)

We recently had a problem in production where a service was filling up the disk, happily swallowing the IOException that was thrown, and continuing on its merry and error prone way. Needless to say, it emptied the input (a high volume redis queue) and produced garbage. We fixed this and then before deployment, needed to create an Out of Disk scenario for testing. My first, clumsy attempt was to fill the disk with the dd command but a few hours later felt very sheepish, as it took quite a while to fill up a large disk (more than half a Terrabyte). The easiest way to do this is to create a loopback partition of a fixed size. Here are the steps I used :

mkdir /filesystems
dd if=/dev/zero of=/filesystems/tmp_fs seek=512 count=512 bs=1M
mkfs.ext4 /filesystems/tmp_fs
mkdir /mnt/small
mount -o loop /filesystems/tmp_fs /mnt/small

This creates a partition of about 1G that gets mounted to /mnt/small. In our scenario, we had to create the Lucene index inside this directory.