Use Python collections.deque instead of list for performance

Leave a comment

Here is a tidbit that Python programmers should be aware of (credit to Although the name list suggests linked list (which has O(1) insert/delete), Lists are implemented as resizable vectors, so insertions & deletions can be O(N). Use collections.deque for O(1) insertions and removals.

import collections
import copy
aList  = list(xrange(10000)) 
aDeque = collections.deque(xrange(10000))
def test1():
   a = copy.copy(aList)
   for x in xrange(len(a)):
      del a[0]

def test2():
   a = copy.copy(aDeque)
   for x in xrange(len(a)):
      del a[0]

python -m timeit -s"import test" "test.test1()"
100 loops, best of 3: 11.4 msec per loop
python -m timeit -s"import test" "test.test2()"
1000 loops, best of 3: 587 usec per loop

Reading From an Android ContentProvider

Leave a comment

Due to changing APIs and (IMHO) non intuitive frameworks, figuring out how to read from a ContentProvider isn’t exactly easy for the uninitiated. Here is some sample code that reads from the Contacts ContentProvider, for posterity.

The previous version of the client ContentProvider API used to synchronously get the data from the ContentProvider (so, doing cross process space IPC and then waiting for the CP to fetch the data from a DB, file, or the web), which could likely cause UI sluggishness due to the blocking of the main thread. The new API uses a LoaderManager, which has its own worker thread to do the work. Communications with the foreground is via some callbacks, which I’m assuming can do UI work from within their context.

// Sorry for the unindented formatting, copy&paste into WordPress’ composer lost all my tabs


package com.example.test;



import android.content.CursorLoader;

import android.content.Loader;

import android.database.Cursor;

import android.os.Bundle;

import android.provider.ContactsContract;

import android.util.Log;

public class MainActivity extends Activity implements LoaderManager.LoaderCallbacks {

LoaderManager loadermanager;

CursorLoader cursorLoader;


protected void onCreate(Bundle savedInstanceState) {





loadermanager.initLoader(1, null, this);



public Loader onCreateLoader(int id, Bundle args) {


cursorLoader = new CursorLoader(this, ContactsContract.Contacts.CONTENT_URI, null, null, null, “display_name”);

return cursorLoader;



public void onLoadFinished(Loader arg0, Cursor c) {



int nameCol = c.getColumnIndex(“display_name”);



Log.d(“TEST”, c.getString(nameCol));




public void onLoaderReset(Loader arg0) {





Understanding the STL’s bind1st() and bind2nd()

Leave a comment

To many people, the bind1st() and bind2nd() functions seem like some kind of mysterious C++/STL voodoo, but its not as arcane as it might sound.

The background here is that we need to convert a function that requires two arguments into a function that requires only one. That function is wrapped into a functor. Recall that a functor is an class which has operator() defined, so it can be called like a function, but can have state (e.g., member variables). This is often used in the context of one of STL’s algorithms.

STL’s algorithms usually operate on unary functions (functions that require one parameter) but we often want to parameterize the said functor with two parameters, and hence need a bridge between these two cases.

So, lets say that you were iterating over some set of values and then wanted to count the occurrences of values for which some condition were true. What we want to do is use STL’s count_if() algorithm. count_if() is a templatized function that takes 3 parameters, the first and second being the begin and end iterators of the collection, and the 3rd must be what is called a UnaryPredicate.

A UnaryPredicate is simply a functor that accepts one argument (which is usually the derefenced iterator), performs some test, and returns the bool result of that test. Simple? Yup. So you could write such a functor that defines:

bool operator() (const typename &valInContainer)
// perform some test on valInContainer and return true/false

In this case, the functor takes just one argument. But what if we wanted to generalize the functor? For instance, what if we wanted to “perform some test on valInContainer” but that test involved some other value. In this case, we could hardcode our constant into the predicate’s operator(). This will work fine, but its not a general approach, since we might need to write another predicate class for a different constant value if that need arose.

In our above code, we could change it as follows:

bool operator()
const typename &valInContainer,
const typename &comparisonValue
// perform some test on valInContainer compared to
// comparisonValue and return true/false

That’s fine, but now we have a binary operator, and what we needed was a unary operator. Ok, so this is where bind1st() and bind2nd() come into the picture. You can use these to create an interface to the operator() that accepts the one parameter but supplies the second parameter. The bind1st() supplies the argument to the first place, so the second one is then the passed in argument, while bind2nd() does the opposite.

So effectively, when you bind1st(foo, 1), you are generating a functor with operator() defined to accept one parameter, but then turns around and calls your foo’s operator() with the value 1 as the first parameter and the accepted paremter as the second. bind2nd does the exact same thing, but with the second parameter being fixed as the argument to the bind2nd() function.

So, knowing this now, you could write the count_if() as,

count_if(container.begin(), container.end(), bind2nd(greater<int>(), 7));

In this case, we have a container that we are iterating over, and use the greater functor and bind the second argument 7 to it, producing a unary functor that compares its input to the value 7. This is then used by count_if to count all elements of said container that are greater than 7.

The STL provides a set of these operator functors, defined at or you can define your own.

boost::lockfree::queue vs stl::queue&posix_mutex

Leave a comment

A quick and dirty test of Boost vs STL with -O3 with both cases not contending for the critical code section.

The results? Both were the same(!). This doesn’t make sense. Boost’s atomics should be faster than a possible drop into the kernel and out to lock and unlock along with a malloc/free.

This needs more investigation to understand whats happening here.

dn-macbook:test davidneiss$ time ./a.out a
real 0m0.168s
user 0m0.156s
sys 0m0.003s

dn-macbook:test davidneiss$ time ./a.out b
real 0m0.162s
user 0m0.157s
sys 0m0.003s

#include <string>
#include <iostream>
#include "boost/lockfree/queue.hpp"
#include <pthread.h>
#include <queue>
#include <assert.h>

using namespace std;

int main(int argc, char *argv[])
const uint32_t NUM_ITERS = 999999;

if (argv[1][0] == 'a')
boost::lockfree::queue<int, boost::lockfree::fixed_sized<true> > queue(10);
for(uint32_t i=0; i<NUM_ITERS; ++i)
int ii;
assert(i == ii);
queue<int> q;
pthread_mutex_t t;
pthread_mutex_init(&t, NULL);

for(uint32_t i=0; i<NUM_ITERS; ++i)

int ii = q.front();

assert(i == ii);

return 0;

Boost tribool

Leave a comment

While diving down into the edges of Boost, I came upon the tribool class, which is a “header only” library. Tribools are bools with 3 states, true, false, and indeterminate. At first, this seems like an unlikely candidate for a general purpose library. However, upon some reflection, there are many cases where such a condition could arise:

  • Hasn’t been initialized yet – you might default something to false, but if its state truely isn’t know yet and it wouldn’t be semantically correct to indicate the false condition, then indeterminate could make sense
  • Transition between states – if there is a delay between states and its important to convey that state uncertainty
  • Failed to complete some operation – if failure needs to be distinct from the true/false state since false itself isn’t semantically correct

Traditionally, dev’s have just held another state variable to indicate the indeterminate state, and if not indeterminate, then consider the boolean value. This works, but why not carry it through and wrap it up nicely by using this type? The only reason that I can think of for not doing this is that if the indeterminate state covered a set of values, then there is extra overhead associated with having each state variable allowing for the indeterminate state (assuming that the indeterminate covers all state variables equally).

The only gotcha that I found when playing with this so far (on my OSX machine, gotta try GNU/Linux)

boost::tribool t1(boost::indeterminate)
t1 == boost::indeterminate // is FALSE!

You have to use indeterminate(t1) // which returns a bool

For those going from Python to C++, consider boost::any

Leave a comment

If you are used to a dynamically typed language such as Python or Javascript and then move to the statically typed language of C/C++, it make take some time adjusting to the static typing concept (but to be fair, for those going from C/C++ to Python, the idea that something can hold differently typed data at different times just seems bizarre and fraught with the chance of type errors, which to be fair, do occur, but not as frequently as a person might think).

In Python, you just declare variables and assign them to whatever typed objects you want. The variables (references) “take on” the type of the data they are referring to. For C++, the boost::any class allows itself to hold various data types, and so you get much of the same behavior as Python’s dynamically typed variables.

As an example of such polymorphic variable using boost:

   using namespace std;
   using namespace boost;
any a;    a = 1; a = string("hello word"); a = 1.1234; a = false;

Ok, so that seems easy enough. What about when you want to extract the data out of the any variable?  The any_cast can be used to effectively cast an any object to the indicated type. If the value contained in the any object isn’t the indicated type however,  then an exception will be throw. You can use the any::type() method to ascertain the contained type before attempting to cast.

For example,

  a = 2;
  cout << any_cast<int>(a) << endl;

  a = string("hello word");
  cout << any_cast<string>(a) << endl;

However, if you tried the following, you would get a run time exception because of the attempted conversion of a string in the any to be converted to an int.

   a = string("hello word");
   cout << any_cast<int>(a) << endl;

BOOST_FOREACH alternative to STL’s std::for_each()

Leave a comment

Once you master the concepts of STL, its time to graduate to the next step, which is Boost. Boost is an incredible set of libraries that are permissively licensed and add a huge amount of functionality. Most of the Boost libraries are header only – they do not require linking with any Boost libraries (making their use one step easier), while just a handful do have backing libs. Additionally, the Boost documentation is written in an easier to understand form than other more turgid references.

An easy Boost library to begin with is Boost:foreach. This is one such library that is “header only”, is simple to grok, and is a great example of how Boost helps you out vs where STL leaves you. Use of this functionality simply requires the inclusion:

#include <boost/foreach.hpp>

Iterating over a container in STL is a common enough operation, using taking the form of:

for(myContainerType::iterator i = myContainer.begin(); 
   i != myContainer.end(); ++i)

Now isn’t that a mouthful just to write a for loop? Compare that to Python’s more succinct expression (“for value in collection:”) and you can see what I’m talking about. C++11 improves on this a bit by having the auto type, allowing the iterator’s type to be automatically deduced by the compiler, so you can do “auto i = my Container.begin()” instead of myContainerType::iterator i = myContainer.being()”.

STL tries to come in and help with their algorithm’s stl::for_each(container.begin(), container.end(), functor). This is a nice improvement, but has the problem of requiring you to express the logic of your for loop within a functor or callback function (as an aside, recall that use of a functor allows for inlining of the functor’s operator() logic, yielding some run time efficiency).

Ok, now lets look at what Boost gives you:

BOOST_FOREACH(type x, containerOfX)
   // do something with x

Now we’re talking. This is much closer to the Python style for loop, moving the logic after the FOREACH statement, which is where you want it. Note that BOOST_FOREACH is actually a macro (if you take offense to the all caps & BOOST prefix, the Boost docs show you how to rename the macro).

In addition, you can write it as “BOOST_FOREACH(type &x, containerOfX)” (eg, by reference) which will allow you to avoid copy construction and modify the value of X in the container.

If you want to iterate in the reverse direction (as STL does by changing the iterators), simply do a BOOST_REVERSE_FOREACH instead.

The brackets (“{ }”) after the BOOST_FOREACH are actually optional, but I prefer it as it helps to ensure that if someone adds an additional line to the body, it’s really included within the body.

You can continue/bail early out of the body, as you can with a regular for loop, using the continue/break statements.

Older Entries


Get every new post delivered to your Inbox.