Nov. 6, 2015, 5:52 p.m.

    Measure Memory Allocation Cost, by Eliminating It

      Over the years, I've learnt to be suspicious of any dynamic allocation in performance critical code, and moving allocations back up the call stack can often yield significant speedups.

      But I'm guilty of being a little religious about this, on some occasions, and this hasn't always been for the best.

      Dynamic allocation helps a lot with writing flexible and robust code. Changing code to remove dynamic allocations can make the code more complicated, brittle, and harder to maintain, and sometimes generalised memory allocation is really just the best tool for the job.

      The first rule of optimisation is to measure. In this post I show how to measure when and where dynamic allocation is actually a significant overhead (and a worthwhile optimisation target), in a simple platform independent way.

      (Sample code is in C++ but the core idea is straightforward and can be applied in other languages.)

      Comments (view full post)

    Aug. 26, 2015, 4:21 p.m.

    Pre-Rendering PDFs for Mobile Devices

      So I wanted to look up some local travel info, the other day.

      There's a detailed PDF file available with exactly the information I need, but my smart-phone really struggles with this heavy-weight PDF.

      Luckily, it turns out to be easy to pre-render the PDF to a big old jpeg and view this image with my phone's built-in image viewer.

      This is so straightforward and convenient, I might as well share the details for the process here.

      Comments (view full post)

    July 29, 2015, 5:07 p.m.

    Vector Meshes

      I remember that when the STL came out, vectors were quite a surprising new way to approach dynamic arrays. In this post we'll look at some of the implications of applying the vector 'paradigm' to a more involved data structure, the dynamic mesh.

      We do a load of mesh processing at PathEngine, both during content-processing and at SDK run-time.

      Sometimes this involves modifying the mesh, and we need dynamic mesh data structures to support this.

      We started out using a traditional pointer-based, 'list-like' mesh data structure, but switched to a 'vector-like' approach, based on contiguous buffers, and from iterators to direct indexing..

      Comments (view full post)

    Feb. 26, 2015, 5:32 p.m.

    Vector Hosted Lists

      Vectors are great when adding or removing elements at the end of a sequence, but not so hot when deleting elements at arbitrary positions.

      If that's a requirement, you might find yourself reaching for a pointer-based list.

      Not so fast!

      Memory locality is important, contiguous buffers are a really good thing, and a standard vector will often out-perform pointer-based lists even where you perform non-contiguous, list-style modifications such as arbitrary element deletion.

      And we can 'host' a list within a vector to get the advantages of a contiguous buffer at the same time as 0(1) complexity for these kinds of manipulations.

      Comments (view full post)

    Oct. 20, 2014, 1:30 p.m.

    Atomic Cross-Chain Exchange

      Cryptocurrencies are great for decentralised payments. Once you have bitcoin you can pay arbitrary destinations without the need to trust in, or get the approval of, any third party.

      But what about if you want to exchange your bitcoin for something else, say another cryptocurrency?

      This normally means registering with a third party exchange service, and trusting that third party service not to lose your funds during the exchange. It's not ideal, and doesn't really fit with the whole decentralised thing!

      It turns out that proper atomic exchange between two cryptocurrencies isn't fundamentally hard, as long as you have the right building blocks, and this is something that I think should then be standardised across different cryptocurrencies.

      Comments (view full post)

    Sept. 26, 2014, 11:38 a.m.

    Infinitesimal Offset Meshes

      In PathEngine, we do a lot of stuff on the surfaces of ground meshes.

      One example is tracking the ground position for a moving agent, which is implemented as traversal along a 2D line through a mesh.

      When coding stuff like this the need to check and handle special case conditions like vertex crossings, or traversal exactly along an edge, can add a lot of complexity.

      In this post I talk about a technique we use in PathEngine, based on an infinitesimally offset mesh model, to eliminate these kinds of special case conditions and simplify our mesh based geometry.

      Comments (view full post)

    July 1, 2014, 3:44 p.m.

    Fast Resettable Flag Vector

      Another custom container post for my Vectors and Vector Based Containers series.

      In this post I'll look at an alternative implementation of the humble bit vector, designed specifically for optimising zero fill operations.

      It's not a new technique, and not particularly complicated to implement, but it's not completely obvious, and it's something that gave us some noticeable speedups when applied to PathEngine so I think it's worth sharing here.

      Comments (view full post)

    June 20, 2014, 2:54 p.m.

    Fast Blockchain Scanning

      (Another post about bitcoin RPC from Python.)

      For certain bitcoin applications you'll need to perform some kind of processing on all of the transactions coming through on the bitcoin block chain. In a bitcoin wallet application, for example, you need to check each new transaction to identify any outputs which are spendable by the wallet, and add the corresponding amounts to the wallet balance.

      In this post we'll look at how to do this with bitcoin RPC calls.

      Theres one obvious way to achieve this, but the obvious approach requires a full transaction index, and also works out to be quite inefficient. I'll show you a less obvious, and more efficient way to do this, without the transaction index requirement.

      Comments (view full post)

    April 7, 2014, 10:02 a.m.

    Bitcoin RPC from Python

      The reference bitcoin client includes a powerful API and RPC interface.

      In this post I show you how to call into this from Python (which is something that turns out to be almost trivially easy to set up).

      Python can work well as a kind of (overpowered) scripting language for automating complicated tasks through the bitcoin reference client, but this is also a great way to get started out if you're interested in writing more involved software that works with bitcoin transactions or the bitcoin blockchain.

      Comments (view full post)

    Jan. 21, 2014, 4:55 p.m.

    Custom Vector Allocation

      (Number 6 in a series of posts about Vectors and Vector based containers.)

      A few posts back I talked about the idea of 'rolling your own' STL-style vector class, based on my experiences with this at PathEngine.

      In that original post and these two follow-ups I talked about the general approach and also some specific performance tweaks that actually helped in practice for our vector use cases.

      I haven't talked about custom memory allocation yet, however. This is something that's been cited in a number of places as a key reason for switching away from std::vector so I'll come back now and look at the approach we took for this (which is pretty simple, but nonstandard, and also pre C++11), and assess some of the implications of using this kind of non-standard approach.

      I approach this from the point of view of a custom vector implementation, but I'll be talking about some issues with memory customisation that also apply more generally.

      Comments (view full post)

    Dec. 22, 2013, 4:41 p.m.

    Zero Initialisation for Classes

      (Number 5 in a series of posts about Vectors and Vector based containers.)

      This is a response to comments on a previous post, roll your own vector, and has also been rewritten and updated fairly significantly since first posted.

      In roll your own vector I talked about a change we made to the initialisation semantics for PathEngine's custom vector class. In my first followup post I looked more closely at possibilities for replacing resize() with reserve() (which can avoid the initialisation issue in many cases), but so far I'm been concentrating pretty much exclusively on zero initialisation for built-in types. In this post I come back to look at the issue of initialisation semantics for class element types.

      Comments (view full post)

    Dec. 20, 2013, 4:39 p.m.

    Avoid resize()?

      (Number 4 in a series of posts about Vectors and Vector based containers.)

      This post is essentially a response to feedback to this previous post.

      In that post I talked about a change we made to the initialisation semantics for PathEngine's custom vector class, and described a specific use case where this can make a difference, with that use case involving calls to the vector resize() method.

      In the comments for that post, Herb Sutter says:

      Thomas, I think the point is that "reserve + push_back/emplace_back" is the recommended style and the one people do use. Really resize() is not used often in the code I've seen; you use resize() only when you want that many extra default-constructed elements, since that's what it's for.

      In this post I'll be looking into our use case in a bit more detail, and in particular whether or not a resize() call is actually required.

      Comments (view full post)

    Dec. 15, 2013, 12:14 p.m.

    Roll-Your-Own Vector

      (Third in a series of posts about Vectors and Vector based containers.)

      STL vectors offer a great combination of dynamically resizing convenience and low level contiguous buffer accessing performance, but std::vector is not the only option, and custom implementations of this container can sometimes be a better fit for your specific requirements.

      Comments (view full post)

    Nov. 22, 2013, 12:45 p.m.

    Efficient Vectors of Vectors

      (Second in a series of posts about Vectors and Vector based containers.)

      STL style vectors are convenient because they hide the details of internal buffer management, and present a simplified interface, but sometimes convenience can be a trap!

      In my previous post I touched briefly on STL vectors with non-simple element types, and mentioned the 'vector of vectors' construct in particular as a specific source of memory woes.

      In this post I'll talk about this construct in more detail, explain a bit about why there is an issue, and go on to suggest a fairly straightforward alternative for many situations.

      Comments (view full post)

    Nov. 18, 2013, 10:39 a.m.

    Using STL Vectors

      (First in a series of posts about Vectors and Vector based containers.)

      STL style vectors are a pretty useful construct.

      I remember coming to C++ (and the STL) from a background in lower level programming, and finding STL vectors a bit surprising, with the idea of amortized constant time complexity and so on.

      And then it was actually something of a minor revolution just to be able to set up a contiguous data buffer, without any significant programming effort, and without knowing the maximum required buffer size in advance.

      Before we had C++ and the STL I remember a common source of errors being dynamically generated data overflowing fixed buffers, which is something we just don't see any more, thanks in no small part to the humble vector (and brethren).

      But convenience can come at a cost, and there's some stuff you need to be careful about when applying STL vectors in performance critical situations.

      In this post I'll discuss the main ways in which STL style vectors are applied in PathEngine, and look at some of the key performance and memory points coming out of this.

      Comments (view full post)

    Nov. 18, 2013, 10 a.m.

    About the Author