Performance Issues With Natural Language Processing in MATLAB
Question: For a class, I'm processing raw text documents (our examples include novels
that can be downloaded from the Gutenberg project) and turning them into a
dictionary data structure. For each word, I need to know which paragraph(s) it
occurs in, and how many times in each paragraph.

The procedure can be divided roughly as

  1. Break document into words, removing whitespace, commas, periods, etc.
  2. For each document, iterate over the words. Look up in dictionary. If the word exists, update its entry. If it doesn't exist, create a new entry.

I'm doing this MATLAB because the rest of my work is in MATLAB and I didn't
want to have to deal with another language/environment. It turns out MATLAB
has some pretty good string processing functions. However, I'm disturbed by
how slow my code is running. The first part I mentioned above is not a
problem; I use a `parfor` loop and it goes pretty fast. The second part is
where my problem is.

My initial attempt at creating this dictionary was to use structs, a MATLAB
built-in data type. The idea was to create a struct called `dictionary`, whose
field names are the actual words, e.g., `dictionary.the` or `dictionary.gnome`
for the words 'the' and 'gnome.' This worked provided the word was a valid
field name (it couldn't be a contraction, for instance). But it ran slow, so I
sought a different solution. My next attempt was to use a `containers.Map`,
which is MATLAB's equivalent of a hash map or dictionary object. (One of my
coworkers informed me that MATLAB is somewhat inefficient at looking up field
names of structs, whereas the hash table has O(1) lookup time.) However,
making this substitution actually _slowed down_ my performance!

At this point, I feel I've some pretty substantial attempts at optimizing my
code and am starting to wonder if MATLAB is really a sensible choice here. I'm
basically trying to figure out whether the slowness is a product of MATLAB or
of me being a terrible programmer (normally MATLAB is quite fast when it comes
to linear algebra, arrays, and matrices). Rather than have someone read over
my code, I'd greatly appreciate whatever feedback the community has to offer
on either of the following:

  * Does anyone do this type of thing (i.e., language processing) in MATLAB or a similar language, such as Python? If so, I'd like to try to benchmark some of my timings. (I've got a MacBook, 2.8 GHz processor, and I'm currently getting about 10-20K words per second.)

  * Is it possible I'd get better results if I switched to a compiled language like Java or C++? Ballpark estimate, what kind of improvement?


Answer: ### My idiosyncratic opinion:

If your project can be nicely split between (1) text, data processing and (2)
mathematical analysis, I'd do all of the former in Java or Python. (Note: I'm
not an NLP guy.)

MATLAB is either amazingly fast (eg. matrix operations using BLAS/LAPACK
libraries) or shocking slow depending on _exactly_ what you are doing.

There's no high performance HashMap solution in Matlab. Compared to what you
can do in C++ or Java, using containers.Map is NOT fast. (I've heard people
advocating using the struct, fieldname hack as a trick to get faster map
performance in Matlab.)

### Quick and dirty, horribly imprecise test:

Inserting 1 million randomly generated, unique strings into a containers.Map
on my machine takes me about 30 seconds:

    
    
    tic();
    for i=1:1000000
        m(x{i}) = i;
    end
    toc();
    Elapsed time is 38.781537 seconds.
    

On the other hand, invoking the java virtual machine and running the code
below takes my machine less than 2 seconds:

    
    
    HashMap<String, Double> hm = new HashMap<String, Double>();
    Random r = new Random();
    for(long i = 0; i < 1000000; i++) {
        hm.put(Double.toString(r.nextDouble()), r.nextDouble());
    }
    
    mgunn@odysseus:~/MATLAB/delme/container_test$ time java ctest
    1.697u 0.151s 0:00.91 202.1%    0+0k 0+1io 0pf+0w
    

Accessing Java objects from MATLAB has a lot of overhead as well...

    
    
    tic();
    h = java.util.HashMap;
    for i=1:1000000
        h.put(x{i},i);
    end
    toc();
    Elapsed time is 53.177989 seconds.
    

### Additional comments

For maximum performance, it's hard to beat highly optimized c/c++ code. Unless
you're extremely familiar with c/c++ though (and even then), you'll end up
having headaches with memory management etc....

For academic coding, excellent vs. OK performance generally isn't so much an
issue. Getting the code correct is more important than speed.

Java or Python are easier languages to code in, with Java tending to have
better performance of the two (but I'm not an expert here).

