I write code

Threads are like shoes

No, seriously!  Hear me out!  Would a 3rd shoe make you run faster?  No - having more shoes than feet really doesn't improve ones performance.  Threads are the same way; if there are more threads than cores, your application isn't going to be any faster either.

In order to explain good and bad uses for threading, we need to first understand the design of computer systems, and how the central processing unit interacts with other subsystems.  In particular, understanding what causes a CPU to stall (wait) is central to efficient threading.

To continue with the silly analogies, let's imagine you are playing chess over the phone.  You can remember a few pieces in your brain, and maybe keep a few more by jotting notes on a small piece of paper, but to check the entire board, you have to talk over the phone to your partner.  This is sort of how a CPU works - it has registers that are extremely quick to access, like your brain, then there is random access memory (RAM), which is like the note paper, and finally, there are IO devices like hard disks or network interfaces that are similar to the phone.  Each one of these tiers takes longer to access, but can store more information.  This is the concept of memory hierarchy - where each layer is further from the CPU and slower to access, but significantly larger than the previous layer.

From the perspective of our software, each CPU core can execute one machine code instruction at a time. The physical reality is more complex, as modern CPUs implement many forms of instruction parallelism, but this simplification does not detract from the overall picture.  Some of these machine code instructions may execute in only a few clock cycles, whereas others may take longer.  The cases we are most interested in for threading are the cases where the CPU is forced to stall, while it is waiting for other, non-CPU resources to respond.  The most obvious cases are disk or network IO, but at the level of the CPU core, main memory access is extremely slow, and even cache access is slow relative to ALU and other in-core processing.

Staying with these simplified models, if a CPU core is spending its time working, and not waiting for input/output of some type, then adding more threads will not increase the throughput of one's program. In fact, it will likely reduce the throughput as there is non-trivial overhead involved in context switching between threads. If the CPU is waiting on other resources, then there is a good chance that more threads will in fact increase throughput - although this is dependent on also ensuring other non-CPU resources do not become a bottleneck.

Rule of thumb: If CPU usage (taskmgr.exe in windows, ps for linux, etc.) is high, adding more threads is unlikely to increase throughput. Conversely, if CPU usage is low and the task can be parallelized, adding more threads may increase throughput.

Omitted details: In order to keep this fairly straightforward, I omitted many details or may have even lied about how things actually work. The most obvious omissions are hyper threading and cache.  Nevertheless, the simplified models here can be used to good effect.

-randy

Change perspective for simplification, part 2

This time we are going to look at the method queuing approach to producer-consumer.  Like last time, we will use C# and asynchronous programming patterns. This implementation requires two queues, one for messages that arrive without an outstanding Consume method call, and a second queue for outstanding Consume method invocations.  Despite the extra queue, to me it is both simpler and more efficient than the message queue only implementation.

        public void Produce(string message)

        {

            AsyncResult ar = null;

 

            lock (protect)

            {

                if (methods.Count > 0)

                {

                    ar = methods.Dequeue();

                }

                else

                {

                    // no waiting method calls

                    messages.Enqueue(message);

                }

            }

 

            if (ar != null)

                ar.Complete(message);

        }

 

        public string Consume(TimeSpan timeout)

        {

            IAsyncResult result = BeginConsume(timeout, null, null);

            return EndConsume(result);

        }

 

        public IAsyncResult BeginConsume(TimeSpan timeout, AsyncCallback callback, object state)

        {

            AsyncResult ar = new AsyncResult(callback, state, timeout);

            string message = null;

 

            lock (protect)

            {

                if (messages.Count > 0)

                {

                    message = messages.Dequeue();

                }

                else

                {

                    methods.Enqueue(ar);

                }

            }

 

            if (message != null)

                ar.CompleteSynchronously(message);

 

            return ar;

        }

 

        public string EndConsume(IAsyncResult result)

        {

            string message = (string)AsyncResult.End(result);

            return message;

        }

This is about the same amount of code as the original approach, but doesn't waste a thread to wait for new messages when clients use the asynchronous methods.  I also find it much simpler to reason about, and thus less likely to have synchronization issues.

-randy

Change perspective for simplification

I was writing some code this afternoon to better understand WCF extension, and had a classic producer-consumer problem. In this case the producer was a networking library, and the consumer was the WCF client application calling Receive or a similar method. On the client side, a user of WCF could call Receive, and if a message had already come in and been queued up, I wanted to return it immediately.  Otherwise it would wait for the next message to arrive, then return it.

My initial approach was to keep a queue of messages, and signal an event whenever a new message arrived on the wire.  Then the Receive method could check the queue, and if it was empty, block on the event.  After a few hundred lines of C# code, this pattern was working for 3-4 different methods, including their BeginFoo/EndFoo asynchronous versions.  Thankfully, I then realized there was a much simpler way - invert the problem, by keeping the waiting methods in the queue rather than the messages.

Not only was this approach more efficient, since I did not need to keep any threads around to wait on the event, it was also much simpler, which will probably significantly reduce the number of threading issues. It probably wouldn't make much difference if I only had synchronous methods, but since I was also implementing asynchronous versions, it made a significant difference.

The interesting methods for the queued message version looked something like this:

        public void Produce(string message)

        {

            lock (protect)

            {

                messages.Enqueue(message);

                messageWaitingEvent.Set();

            }

        }

 

        public string Consume(TimeSpan timeout)

        {

            DateTime absoluteTimeout = DateTime.Now + timeout;

 

            do

            {

                if (messageWaitingEvent.WaitOne(timeout))

                {

                    lock (protect)

                    {

                        try

                        {

                            return messages.Dequeue();

                        }

                        catch (InvalidOperationException)

                        {

                            // the queue is actually empty

                            messageWaitingEvent.Reset();

                        }

                    }

                }

 

                timeout = absoluteTimeout - DateTime.Now;

            } while (timeout > TimeSpan.Zero);

 

            throw new TimeoutException();

        }

Most of the complexity is in the consumer; the producer is very simple in this approach.  The asynchronous methods were implemented with a delegate on the synchronous Consume method.  Very simple, but not especially elegant:

        private Func<TimeSpan, string> asyncConsume = new Func<TimeSpan, string>(Consume);

 

        public IAsyncResult BeginConsume(TimeSpan timeout, AsyncCallback callback, object state)

        {

            return asyncConsume.BeginInvoke(timeout, callback, state);

        }

 

        public string EndConsume(IAsyncResult result)

        {

            return asyncConsume.EndInvoke(result);

        }

I cheated slightly above to keep the sample short - the initialization of asyncConsume must be handled in the constructor, not a field initializer.  I'll post the method-queuing solution next.

-randy

Efficient file format for read only records, part 2

Last time we described the basics of the file format, and wrote some sample code to generate the file.  This time we are going to read the file. The process consists of skipping to the end to read the number of entries, then jumping back and reading the entire index section into memory.  Once that is done, we are ready to perform lookups, by binary searching the index section for the desired key, then performing one seek and read to load the corresponding data record. The interesting parts follow:

void load_index(std::vector<index_record>& index, std::istream& stream)

{

    unsigned int size;

    stream.seekg(0 - sizeof(unsigned int), std::ios_base::end);

    stream.read(reinterpret_cast<char*>(&size), sizeof(size));

 

    index.resize(size);

    stream.seekg(0 - sizeof(unsigned int) - sizeof(index_record) * size, std::ios_base::end);

    stream.read(reinterpret_cast<char*>(&index[0]), sizeof(index_record) * size);

 

    if (!stream.good())

        throw format_error("stream is bad");

}

 

bool lookup(unsigned int key, const std::vector<index_record>& index, std::istream& stream, data_record* pRecord)

{

    index_record rec;

    rec.key = key;

 

    std::vector<index_record>::const_iterator pos = std::lower_bound(index.begin(), index.end(), rec, index_record_order);

    if (pos == index.end() || (*pos).key != key)

        return false;

 

    stream.seekg((*pos).offset);

    stream.read(reinterpret_cast<char*>(pRecord), (*pos).length);

 

    return true;

}

Usage is very straightforward:

    std::ifstream file("file.dat", std::ios_base::in | std::ios_base::binary);

    std::vector<index_record> index;

 

    load_index(index, file);

 

    data_record record;

    if (lookup(key, index, file, &record))

    {

        // process the record with 'key'...

    }

    else

    {

        // no such record...

    }

The STL function lower_bound implements the binary search algorithm, and is used by lookup() to search the index. Don't be fooled by the simplicity of binary search - it is extremely efficient. 4 billion records can be searched with 32 comparisons.

Next time we will look a some possible improvements, including refactoring the sample functions into a nice design, compression, caching, and a few other ideas as well.

-randy

Efficient file format for read only records

Selecting a good file format can make a huge difference in a system.  Certainly file formats focused on sharing and standards, such as XML and JSON, get lots of attention, but there is equally important work at the other end of the spectrum - private data files.  The format outlined here is designed for internal use, and is particularly well suited to sequential build, with random access.  It also scales well to large data sets, limited by the ability to keep the record index in memory.

The basic idea is as follows:

Header (version, etc)/TD>

Data record 1

Data record 2

...

Data record n

Index record 1

Index record 2

...

Index record n

Index count

The data records can be any format you like, fixed or variable length, it really doesn't matter.  The index records need to be of fixed size, and should be padded to match the native alignment of your chosen CPU architecture.  Each index record needs to include the offset and size of the corresponding data record, and the key.  Something like this:

        struct IndexVariableRecord

        {

            UInt32 key;

            UInt32 dataLength;

            UInt64 dataOffset;

        }

The types you choose to use should obviously be selected to match the type of data, and the overall size of the collection.  Here I am assuming variably sized records, a 32-bit unsigned integer key, a possibly huge file (the 64-bit offsets), and a maximum individual record size of 4GB.  In most cases one probably needs more bits for key, and fewer for capacity.  A sample index structure for fixed size data records could be:

        struct IndexFixedRecord

        {

            UInt32 key;

            UInt32 dataIndex;

        }

Here we are using the same 32-bit key, but now are using an index into the record portion of the file, rather than an offset and length. In this case the offset can be computed, with "sizeof(FileHeader) + sizeof(DataRecord) * indexRecord.dataIndex".  The length is then simply sizeof(DataRecord).

In order to allow efficient access, the index records should be sorted by key.  To keep the build process simple, it is not necessary for the index and data records to be in the same order - this allows one to easily generate very large data files quickly.

Generation of such a file is a fairly simple process.  It involves building the index section in memory, while writing the data section to disk. When finished, the entire index section can be sorted, and then written to disk.  Something like this in C++:

// maximum valid size for the variable portion of a data_record

const unsigned int max_data_record_variable_size = 64 * 1024;

 

#pragma pack(push, 1)

struct data_record

{

    unsigned int fixed_data;

    // more fixed fields...

    unsigned char variable_data[max_data_record_variable_size];

    // this portion can be any length

};

 

struct index_record

{

    unsigned int key;

    unsigned int length;

    unsigned long long offset;

};

#pragma pack(pop)

 

// write a data record in binary format

void write_data_record(std::ostream& out, const data_record& record)

{

    out.write(reinterpret_cast<const char*>(&record.fixed_data), sizeof(record.fixed_data));

    out.write(reinterpret_cast<const char*>(&record.variable_data[0]), record.fixed_data);

}

 

unsigned int get_key(const data_record& record)

{

    return record.fixed_data;

}

 

bool index_record_order(const index_record& a, const index_record& b)

{

    return a.key < b.key;

}

 

// write a simple binary file header, consisting of a signature and version

void write_header(std::ostream& stream)

{

    static const unsigned int signature = 0x52544b46;

    static const unsigned int version = 0x00000009;

 

    stream.write(reinterpret_cast<const char*>(&signature), sizeof(signature));

    stream.write(reinterpret_cast<const char*>(&version), sizeof(version));

}

 

template<class _itor>

void write_data_file(const char* filename, _itor begin, _itor end)

{

    std::ofstream datafile(filename, std::ios_base::out | std::ios_base::binary);

    std::vector<index_record> index;

 

    write_header(datafile);

 

    for (; begin != end; ++begin)

    {

        const data_record& record = *begin;

 

        std::ofstream::pos_type beginPos = datafile.tellp();

        write_data_record(datafile, record);

        std::ofstream::pos_type endPos = datafile.tellp();

        if ((unsigned long long)std::numeric_limits<unsigned int>::max() < endPos - beginPos)

            throw std::overflow_error("single record was too long");

 

        index_record indexRecord;

        indexRecord.key = get_key(record);

        indexRecord.offset = beginPos;

        indexRecord.length = static_cast<unsigned int>(endPos - beginPos);

 

        index.push_back(indexRecord);

    }

 

    std::sort(index.begin(), index.end(), index_record_order);

 

    unsigned int size = index.size();

    datafile.write(reinterpret_cast<const char*>(&index[0]), sizeof(index_record) * size);

    datafile.write(reinterpret_cast<const char*>(&size), sizeof(size));

}

Calling this would look something like:

    std::vector<DataRecord> dataRecords;

    // get records...

 

    write_data_file("file.dat", dataRecords.begin(), dataRecords.end());

Any input iterator will work, it doesn't have to be a vector - thus you can stream records from another file directly into the builder, only keeping the index in memory:

    std::ifstream input("records.txt");

    std::istream_iterator<data_record> itor(input);

    std::istream_iterator<data_record> end;

 

    write_data_file("file.dat", itor, end);

Although there is quite a bit of code here, if we break it down it is pretty easy to follow:

• Structure definitions for the data record and index record. Note the use of #pragma pack to ensure the structures in memory layout is exactly as desired.
• write_data_record: a very simple function to serialize a data_record to an std::ostream in a binary format.
• get_key: used to extract the key from a data_record when building the index.
• index_record_order: used to sort the index records, so we can use binary search later.
• write_header: by including a signature and a version number, we can more easily tell during read if a file is valid or not. 
• write_data_file: the heart of the sample, this takes the filename for the data file, and a pair of iterators to data_record's:
  • Create the output file using std::ofstream.
  • Declare a std::vector to build the index in memory.
  • Write the file header.
  • Enumerate each data record:
    • Store the current file position.
    • Write the data record, using write_data_record.
    • Compare the new file position with the stored position, and ensure that it is small enough to fit in the length member variable of index_record.
    • Construct a new index_record, using the key extractor (get_key), the offset, and computed record length.
    • Add the index_record to the in-memory collection.
  • Once we process all of the data records, sort the index collection using the predicate index_record_order, which simply sorts by ascending key.
  • Write the index section to disk.
  • Write the count of index records to disk.

Next time we will implement a simple class to load and access this data file.

-randy

Reading arrays from files in C# without extra copy

A friend of mine was talking about an application he wrote, and mentioned that reading the data file was a bit painful. He used the System.IO.BinaryReader class, and called the relevant method for each and every field.  It probably went something like this:

        static MyStruct[] ReadStructArray1(Stream file, int count)

        {

            MyStruct[] results = new MyStruct[count];

            using (BinaryReader reader = new BinaryReader(file))

            {

                for (int i = 0; i < count; ++i)

                {

                    results[i].field1 = reader.ReadInt32();

                    results[i].field2 = reader.ReadInt32();

                    // etc...

                }

            }

 

            return results;

        }

The drawback is you have to write many lines of code, keeping them in sync with the structure definition, and it is inefficient.  You won't be able to get anywhere near the sequential disk read rate with this approach.  I came across this post by Eric Gunnerson, which outlines a technique that at least removes the repetitive lines, at the cost of unsafe code:

        static unsafe MyStruct[] ReadStructArray2(Stream file, int count)

        {

            MyStruct[] results = new MyStruct[count];

            int structSize = sizeof(MyStruct);

            byte[] buffer = new byte[structSize];

            for (int i = 0; i < count; ++i)

            {

                if (file.Read(buffer, 0, structSize) != structSize)

                    throw new InvalidDataException();

 

                fixed (byte* pBuffer = buffer)

                {

                    results[i] = *(MyStruct*)pBuffer;

                }

            }

 

            return results;

        }

This is better, but results in small reads (a struct at a time), and an extra memory copy from the buffer into the struct.  This still won't be able to drive the disk at full speed, although should be faster than the first approach, at least if the struct is fairly large and includes a meaningful number of fields.  One significant limitation of this solution is that the struct must be unmanaged - i.e. it must be a value type, such as a struct, and all fields must also be value types.

It is relatively easy to extend this to read directly into the array of structures.  At first I tried using the various Read methods on Stream or related classes, but they all expect a byte array, instead of a byte*, and I don't believe one can cast a MyStruct[] into a byte[] (which intuitively makes sense - since the size of each element is different between a byte[] and MyStruct[], how would the Length property work?  this of course in addition to other problems).

By using P/Invoke to call the Win32 API ReadFile, we can use a byte* for the buffer, which is an easy cast from our MyStruct[]:

        static unsafe MyStruct[] ReadStructArray3(SafeHandle file, int count)

        {

            MyStruct[] results = new MyStruct[count];

            fixed (MyStruct* p = &results[0])

            {

                byte* p2 = (byte*)p;

 

                UInt32 cbReadDesired = (UInt32)(sizeof(MyStruct) * count);

                UInt32 cbReadActual = 0;

                bool ret = ReadFile(file, p2, cbReadDesired, &cbReadActual, null);

                if (!ret || cbReadActual != cbReadDesired)

                    throw new InvalidDataException();

            }

 

            return results;

        }

This implementation avoids any extra memory copies, beyond what the OS and disk subsystem need. There are a few points worth discussing in this implementation:

• MyStruct must be unmanaged, just as with ReadStructArray2.
• Use of the "fixed" statement: this was used in ReadStructArray2 also, but I didn't explain it.  It is used to keep the runtime from moving the results array in memory, which would obviously cause the ReadFile function to do strange things (corrupting random bits of your program, resulting in crashes or worse).
• SafeHandle - this class was added in .NET 2.0, and is a significantly better way to use OS handles than IntPtr. You can get a SafeHandle for a file from the FileStream.SafeFileHandle property.
• The in-memory layout of the structure must match the on disk layout; in particular padding may be a problem.  See System.Runtime.InteropServices.StructLayoutAttribute for a solution to this problem.

The declaration for ReadFile is as follows:

        [DllImport("kernel32", SetLastError = true)]

        private static extern unsafe bool ReadFile(

            SafeHandle hFile,

            byte* lpBuffer,

            UInt32 nNumberOfBytesToRead,

            UInt32* lpNumberOfBytesRead,

            System.Threading.NativeOverlapped* lpOverlapped);

Next was a quick test driver that reads a 1GB file.  Each approach was run 10 times, the low and high were tossed out, with the average of remaining values listed below:

ReadStructArray1	9650 ms
ReadStructArray2	3900 ms
ReadStructArray3	1650 ms

-randy

Optimizing the C# rewrite

Last night I got a little time to profile the C# implementation of the serialization library that we evaluated in the previous post. With one good optimization and one gross one, I was able to get the C# implementation to execute in less time than the native C++ implementation.

The good optimization was adding a "thicker" method to the buffer manager, thereby allowing us to do a few things at once: grow the buffer if needed, set the new length, and return the buffer, all in one call.  The gross optimization involved manually inlining the most commonly used methods, so that a duplicate call could be removed.  A call graph may help explain this second optimization:

ClientCode
    WriteProperty
        WritePropertyHeader
            GetAndGrowBuffer
        WritePropertyValue
            GetAndGrowBuffer        

By manually inlining the implementation of WritePropertyHeader and WritePropertyValue inside WriteProperty, one can remove one of the two calls to GetAndGrowBuffer. This change results in "shared" code now being littered across all of the WriteProperty overloads, resulting in a poor tradeoff of maintainability for performance.  Only in the most critical situations would I ever tradeoff maintainability for performance.

As a reminder, here are the numbers from before:

Native	90 ms
Managed C++ wrapper	130 ms
C# rewrite	230 ms

The optimized version:

Optimized C# rewrite

75 ms

This is now 15% faster than the native implementation!  I gave back some of the time to use System.String, rather than hiding the UTF-8 conversion cost like we did last time.  That version is roughly 10% slower than native, a very small price to pay:

Optimized C# rewrite, w/String

100 ms

This isn't a fair fight, since I did not take time to optimize the native or C++ wrapper implementations.  But it does illustrate that performance should not be the deciding factor when making these C++/Managed C++ wrapper/C# rewrite tradeoffs.

-randy

Managed C++ wrapper vs. C# rewrite

My group has recently been adding support for managed applications to our platform. As part of this work, we are experimenting with various approaches - rewriting existing libraries in C#, writing managed wrappers for native libraries in Managed C++, DllImport, etc.

Although the best approach varies depending on the specifics, such as the stability of the underlying C++ library, how closely the programming model in the C++ library matches that of .Net, and even our plans for the future of the component, the performance aspects of each approach has been a constant question.

One of the first libraries to be incorporated was a networking library.  This is a fairly complex, ~10,000 line C++ library with lots of threading, memory management, and sockets programming. Relatively complex, and a treasure trove of subtle bugs that we have worked out over the course of several services and multiple years.  The choice to wrap this library with a thin managed C++ assembly was easy - given that the interface is fairly simple (only a handful of APIs, and each one does something rather large and complex, like "send message"), and the implementation is complex.  With some clever pinning and hooks into the native library, we were able to make this work very smoothly from .Net, while still providing great performance, and without introducing lots of defects from a rewrite.  The performance difference between managed clients and native clients of this library is under 5%.

I had wondered if a different approach would be needed for a "chatty" API, something where the client makes many function calls, each of which does a relatively small amount of work. I chose our serialization library for this experiment, as it is fairly small (~2,500 lines of code) and very chatty - each method rarely does more than copy a few bytes into a buffer.

To test this scenario, I wrote both a managed C++ wrapper for the serialization library, as well as a C# port.  I kept the interface exactly the same between the wrapper and port, and the implementation of the original library and port are as close as possible.

After writing the new library and wrapper, I took some real serialization code from one of our clients, and converted it into 3 test drivers; a native C++ implementation that uses the original library, a C# version that uses the managed wrapper, and a C# version that uses the port.  The messages generated by the sample code are about 20KB in size, each message consists of roughly 600 properties, and the test generates 1000 messages.

Results for the first test:

Native	90 ms
Managed C++ wrapper	300 ms
C# rewrite	350 ms

Wow...  the penalty for a managed application is over 200%, and nearly 300% for the C# rewrite.  There was one significant difference between both managed implementations and the original, native C++ library - string handling.  The serialization format specifies UTF-8, and the native clients traditionally use UTF-8 internally as well.  Therefore the managed implementation had to convert from the Unicode System.String into UTF-8 for every string property, whereas the native implementation simply copied bytes.

To remove this difference, I wrote a second version of the test client that converted all of the string values to UTF-8 byte arrays once, outside of the timed section, then passed the pre-encoded byte arrays to the serialization library:

Native	90 ms
Managed C++ wrapper	130 ms
C# rewrite	230 ms

This puts the managed C++ wrapper within 50% of the native implementation, with an additional 75% for the C# rewrite.  Given that the managed C++ wrapper is only a couple hundred lines of code, and took less than an hour to write, it seems like the best choice.

As a general observation, the real decision here should not be made on the basis of performance alone.  Even comparing the best to the worst implementations only adds 1/4 of a millisecond - a quantity that in nearly every situation will be dwarfed by other factors. Using System.String is probably worth 0.26ms.

In the future I would like to profile and optimize the C# rewrite, to see how close to the native implementation we can get.

-randy