The most efficient string buffering

Question

I met a requirement in my current project, which led me to the necessity of a buffering method for a unicode symbols sequence with minimal time cost. Basic operations for such buffer are:

• Reading its value as a unicode string
• Appending a symbol to the tail of the buffer
• Flushing the buffer

Therefore, I tested a few approaches to find the one with the minimal timing overhead, but I'm still not sure if I got the fastest one. I tried the following algorithms (listed from the most efficient):

1. A list of symbols
2. io.StringIO object
3. Naive string storing
4. Preallocated array.array

Can anyone give me a hint on a better approach for this challenge? The project interpreter is CPython 2.7. The MCVE for my test is:

# -*- coding: utf-8 -*-

import timeit
import io
import array
import abc


class BaseBuffer:
    """A base abstract class for all buffers below"""
    __metaclass__ = abc.ABCMeta

    def __init__(self):
        pass

    def clear(self):
        old_val = self.value()
        self.__init__()
        return old_val

    @abc.abstractmethod
    def value(self):
        return self

    @abc.abstractmethod
    def write(self, symbol):
        pass


class ListBuffer(BaseBuffer):
    """Use lists as a storage"""
    def __init__(self):
        BaseBuffer.__init__(self)
        self.__io = []

    def value(self):
        return u"".join(self.__io)

    def write(self, symbol):
        self.__io.append(symbol)


class StringBuffer(BaseBuffer):
    """Simply append to the stored string. Obviously unefficient due to strings immutability"""
    def __init__(self):
        BaseBuffer.__init__(self)
        self.__io = u""

    def value(self):
        return self.__io

    def write(self, symbol):
        self.__io += symbol


class StringIoBuffer(BaseBuffer):
    """Use the io.StringIO object"""
    def __init__(self):
        BaseBuffer.__init__(self)
        self.__io = io.StringIO()

    def value(self):
        return self.__io.getvalue()

    def write(self, symbol):
        self.__io.write(symbol)


class ArrayBuffer(BaseBuffer):
    """Preallocate an array"""
    def __init__(self):
        BaseBuffer.__init__(self)
        self.__io = array.array("u", (u"\u0000" for _ in xrange(1000000)))
        self.__caret = 0

    def clear(self):
        val = self.value()
        self.__caret = 0
        return val

    def value(self):
        return u"".join(self.__io[n] for n in xrange(self.__caret))

    def write(self, symbol):
        self.__io[self.__caret] = symbol
        self.__caret += 1


def time_test():
    # Test distinct buffer data length
    for i in xrange(1000):
        for j in xrange(i):
            buffer_object.write(unicode(i % 10))
        buffer_object.clear()


if __name__ == '__main__':

    number_of_runs = 10
    for buffer_object in (ListBuffer(), StringIoBuffer(), StringBuffer(), ArrayBuffer()):
        print("Class {klass}: {elapsed:.2f}s per {number_of_runs} runs".format(
            klass=buffer_object.__class__.__name__,
            elapsed=timeit.timeit(stmt=time_test, number=number_of_runs),
            number_of_runs=number_of_runs,
        ))

... and the results I've got for this run are:

Class ListBuffer: 1.88s per 10 runs
Class StringIoBuffer: 2.04s per 10 runs
Class StringBuffer: 2.40s per 10 runs
Class ArrayBuffer: 3.10s per 10 runs

Answer 1

I tried a couple of alternatives (see below), but I wasn't able to outperform the ListBuffer implementation. Things I've tried:

Non-pre-allocated array

class ArrayBufferNoPreallocate(BaseBuffer):
    """array buffer"""
    def __init__(self):
        BaseBuffer.__init__(self)
        self.__io = array.array("u")

    def value(self):
        return self.__io.tounicode()

    def write(self, symbol):
        self.__io.append(symbol)

Numpy

class NumpyBuffer(BaseBuffer):
    """numpy array with pre-allocation"""
    def __init__(self):
        BaseBuffer.__init__(self)
        self.__io = np.zeros((1000000,), dtype=np.unicode_)
        self.__cursor = 0

    def clear(self):
        val = self.value()
        self.__cursor = 0
        return val

    def value(self):
        return np.char.join(u"", (self.__io[i] for i in xrange(self.__cursor)))

    def write(self, symbol):
        self.__io[self.__cursor] = symbol
        self.__cursor += 1

Results

Class ListBuffer: 3.40s per 10 runs
Class StringIoBuffer: 4.44s per 10 runs
Class StringBuffer: 4.58s per 10 runs
Class ArrayBuffer: 4.65s per 10 runs
Class ArrayBufferNoPreallocate: 3.94s per 10 runs
Class NumpyBuffer: 5.73s per 10 runs

If you really want substantial speed improvements, you might have to write a c extension or use something like cython.

If you can optimize your problem so that it doesn't require a function call for each character, you could gain some performance as well.