In BSONEncoder.putObject(), the core field put loop is:
for ( String s : o.keySet() ) {
// ...
_putObjectField(s, o.get(s));
}

For Map-based implementations of DBObject/BSONObject (the defaults), this is a fast operation. However, if the underlying data isn't directly stored in a Map (but in a List or some other non-random-access data structure), this is relatively inefficient.

There are two potential solutions to this:
1) Pull the Map and iterate over the entrySet() of the underlying Map
2) Add a Set<Entry> entrySet() method to BSONObject

#1 is the solution which doesn't involve backwards incompatibility (as it doesn't involve adding a new method on BSONObject which would have to be implemented by all subclasses), but #2 would be the cleanest in comparison with the existing code.