I recently came around to thinking that not working full time at age 60 after a 45 year career didn’t make me a slacker and that I might actually enjoy some of those things that I hear retired people do.
I had more or less the same epiphany 8 years ago but it didn’t stick. I found myself spending a lot of spare time coding anyway and started to wonder “hey, didn’t I used to get paid for this, not have to buy my own health insurance, and (most importantly) have customers actually run my code?”. This time I think it will stick though.
My home office has a 100GB ethernet cluster with >512 cores, a bunch of GPUs, a large format fine-art printer, and a serious set of electronic and mechanical tools. So I do have plenty of ideas for things I want to work on, and people to collaborate with, but they are more likely to show up on github, or one-off personal projects than commercial games.
I will probably try to figure out this “open source” thing where you write code and then give it away (???). I’d have ended up homeless if people didn’t pay me for my code :-).
Since I’ve got a lot more time for random stuff now, I’d like to say that I’m available for presentations about etc about stuff I’ve been involved with. I’ve generally not pursued this in the past. I’ve never even gone to an Amiga retro event even though I still have a boing jacket :-). Here’s a link of me talking about Ultima Underworld and predecessors at one thing https://www.youtube.com/watch?v=xn76r0JxqNM,
The game industry has been very good to me and I’d like to give back. I’m willing to do random small consulting for small indy game developers, such as join technical meetings, explain algorithms/math, or work on small optimization/etc problems for the price of a pizza (or less) instead of my usual price-of-a-lot-of-waygu :-).
I’m mostly interested in working on my own self-directed stuff, but I wouldn’t absolutely rule out really interesting commercial things. It would have to be short term because I’m not planning on going long stretches between scuba trips :-).
A very useful system to have, especially in large codebases (including in game development) is an automated unique symbol generator. A unique symbol is a mapping from a textual identifier that has the following properties:
At execution time, symbols are stored and passed around as a simple primitive type which can be efficiently passed by value and compared numerically. This means it is an integer or pointer type.
Symbols can be used in code without being declared separately.
Symbols with the same name declared in one module (a .lib, .dll or .cpp file) hold identical values.
Symbol names can also come from data files at runtime.
Symbols are strongly typed. This prevents errors and also allows automatic type conversions from strings if desired.
These can be thought of as corresponding to either LISP style symbols (which are represented as unique pointers) or “magically defined” enums. I have implemented and used such a system multiple times in different codebases, using different tehniques:
I wrote the rules system for Magic the Gathering Online, which was the first (maybe still the only?) code implementing the full exact rules of MTG. Because in Magic, any game object (a card, a spell on the stack, a continuous or triggered effect, the player status, etc) can have an arbitrary set of properties, including overlaying properties from other objects on it, such as enchantments that change the enchanted creature, end of turn effects, etc. There are many thousands of possible properties, and every new card set creates more. In addition, you have to encode arbitrary matching operations, and other cards have to be able to even modify the _queries_ (for instance changing color words). Given this, a struct holding all the properties of a game object like a card would not work – the struct would be massive and ever-changing as many properties only appear on a small number of cards, and the struct would have to be annotated for things like serialization (the game state sent to client computers consisted of these property lists, transmitted as deltas). So there was one class (I don’t have the code anymore but I called it something like a “MTGThing” or “MTGObject”). The description of something like a Forest would be a property list, created at init time from a c++ array (note that this was written pre-c++11, so some choices for implementation weren’t available). All unique ids used a unique prefix of MA_ so it looked something like this:
Each MA_ value would map to a uniquely determined integer definition. Because symbols were exchanged between client and server and stored in data files, the integer representation had to be the same between multiple runs and storable. The “week-long crunch” demo that got us the contract actually used a server written by me in Lisp in order to get it working quickly (I switched to c++ for the rules when I started the “real thing” for multiple reasons) so I tried to map the c++ concepts closely to lisp s-expressions/property lists.
I implemented a completely different symbol system in a game engine at Valve where it was used for several things. One instance was for connecting between code and materials/shaders. Shaders are written separately and can be loaded dynamically. but c++ code might want to set a property looked at by a shader, without having to add and maintain a settings struct for each shader. It is also desirable to set a property on a draw call that a shader can see, but which it might ignore because the particular shader doesn’t have that option, but others used on similar objects might. This system uses a string syntax for tokens in the code like Renderer()->SetProperty( “numFilterTaps”, 4 ) (not actual code). Underlying this is a class for the symbol that converts the string to a hash value.
In my personal codebase developed during my hiatus from Valve, a very different integer-based system was used, which I think is my favorite implementation.
Implementation methods
There are many ways to implement such a system, with various tradeoffs. Nice properties to have are:
Efficiency. String->symbol conversions should happen either at (ideally) compile time or initialization time.
Debuggability. There should be a practical way to map a token back to the string. If you don’t wish to store the actual string in the code, this could be a generated table, ideally hooked up to a debugger visualization.
Information hiding. You might wish for null terminated strings to NOT show up in the executables, just the identifiers. This can conflict with debuggability.
Persistence of values across different runs or changes in the definitions. You may wish to be able to serialize the actual identifier values. Using pointers for the symbol may preclude this.
Fast compilation. Compile-time versions which rely on either compiler inlining or constexpr may cause a high compilation cost if used broadly.
Performance stability. compile-time conversion between strings->symbols may end up as run-time conversion in a debug build or in different compilers.
Ease of build process.
IDE/editor features: Ideally, symbol references are recognizable by simple regular expression matching so that they can be displayed with customizable colorization or font styling. In addition its very valuable for them to be able to be auto-completed.
Compile time hashing of string literals
The simplest implementation is one that relies on the compiler to do everything, with no external tools or separate steps. Since there is no way at compile time to build tables or allocate identifiers (especially between separately compiled modules), you need to choose a symbol representation that is directly mapped from the string literal to a numeric code. One way is to implement numeric hashing of the characters in the literal, using hashing code that can be evaluated at compile time. I implemented such a system at Valve many years ago. Since this was before c++ got things such as constexpr and consteval, I did it by carefully constructing my hashing code in such a way that the major compiler’s optimizers would evaluate the hash codes at compile time, simply emitting numeric literals. It was important that use of the symbols would be simple, so it was implemented using a class that could auto convert from a string literal. In order to coax the compiler into evaluating the hash at compile time, it was necessary (at the time) to avoid any looping over characters. My solution was to implement a different constructor for every input string length. I did this by writing a script to generate the code for a loop-free murmur hash for each possible input size (in this example I use a simple sum of chars to illustrate):
You can see this code in action here. things to observe are:
In the optimized code, the actual string characters do not appear and the compiler just passes simple integers around in registers.
In a non-optimized debug build, You will lose the compile-time evaluation and every usage will perform a loop over the characters at runtime on every call.
There is no way to convert the hash code back to the source string without additional annotation, which can be quite a hindrance in debugging. This maybe implemented via a dictionary or actually storing the string as part of the symbol in debug builds.
With any hash code, collisions are a possibility, and will be undetected without additional instrumentation.
There is no easy way for the IDE to highlight the symbols as their usage just looks like string literals. One possible solution to this is to use user-defined string literals with their own assigned suffix, instead of ordinary strings.
The actual symbol type ends up not being a primitive integer or pointer type, but a struct. This has implications for code generation and parameter passing.
With a complex hash function used widely, you may see a significant impact on compilation time.
The resultant symbols cannot be used as labels in switch statements.
Many IDEs/editors (Emacs is an exception) will not do autocompletion in string constants, meaning that you will have to type every symbol name when you use it and be prone to typos.
Preprocessing based methods
At the expense of some build complexity, a source code scanner can be used to generate definitions for the tokens in .h files. It is quite easy to incorporate such a build step into your compilation using the “prebuild step” functionality in CMake or Visual Studio to extract definitions from the source files. What we are going to do is write a simple program to scan a set of source files and output a .h file defining values for all symbols encountered. In order to make this simple and not require a full c++ parser, a syntax for symbol names that can easily be matched by a regular expression is used. Such a program could be written in a simple script language or even as a shell script, but I chose to write mine in C++.
This is the mechanism that I used for Magic Online. Unique symbols were proceeded by MA_, and a scanner was written that would scan all source files (and data files) to produce a global .h file full of #defines, defining each as an integer value.
The reason that data files needed to be scanned as well as code files was that every observed symbol was assigned a new unique sequential id the first time it was seen by the scanner. Version control was used on the generated .h file in order to atomically assign new values and keep track of all that had ever been seen. Data files have to be scanned as this approach (unless something like a hashing approach) is not capable of defining new symbols at run time.
What to generate for symbols?
So suppose our symbol scanner sees a reference to a symbol MA_STRENGTH and takes note of it. What should it produce in the output file?
One factor is that we want to handle multiple symbol definition files (for instance for different projects or libraries) which may contain duplicate (but identical) definitions. So we will bracket every definition by
One possibility for what to define symbols as is to define them as pointers to a symbol struct looked up by name at initialization time. This has the advantage of making it easy and efficient to associate data (such as symbol name) with each symbol. This does incur a startup cost and prevents things like using symbol names in case statements though:
Instead in my current system, I define Symbol_t’s as 64 bit enums, and assign a deterministic value to each symbol based upon its name:
enum class Symbol_t : uint64_t
{
NIL = 0,
INVALID = ~0ull
};
#ifndef SYM_MA_STRENGTH_DEFINED
#define SYM_MA_STRENGTH_DEFINED
constexpr Symbol_t MA_STRENGTH = Symbol_t( 0x55aa348978 ); //Hash function calculated by preprocessor
#endif
This has the advantage of being able to perform any hash function without requiring that the compiler be able to evaluate it at compile time, and not paying the price of evaluating a lot of constexpr functions during compilation. It does have the disadvantage of possible hash collisions and also not being able to recover the symbol name from the enum value without outputting some sort of dictionary at preprocessing time.
My solution: using radix 50 to prevent collisions and allow reverse mapping
In my personal codebase, I use a different approach instead of either a hash code or an allocated unique id. Since I am using a 64-bit enum value to represent the symbol, I have 8 bytes to store a mapping from name to integer. An obvious approach would be to just pack the first 8 characters of the symbol name into the 64-bit word, producing a unique symbol id for every symbol that differs in the first 8 characters, and allowing easy conversion from the numeric form back to the string form. If we cap the max symbol name length at 8 characters, we never have to worry about a collision. But, we can do better than 8 characters by limiting the character set usable in symbol names. In particular if we limit them to the set of legal C identifier characters and make them case insensitive, we can use an encoding with only 40 possible characters (a-z, 0-9, _, and a nul/blank character, giving us a set of 38 characters with 2 left unused). What is so special about the number 40? The answer is that 40*40*40 = 64000, which is less than the 65536 possible values in a 16-bit word, allowing us to pack 3 characters into 2 bytes or 12 characters into 8 bytes (with lots of left over invalid values to use for special purposes). Or, if we desire to have a few “flag bits” available in the symbols, we could give up one significant character by using the lower 5 bits of the int64_t for flags. We will create the following encode/decode functions for use both at runtime and in the preprocessor.
// It doesn't matter for compile-time defined ones, but for dynamically loaded symbols, it is
// possible to write much better versions of this, using either tables or SIMD.
constexpr int ToRadix50( char c )
{
if ( ( c >= '0' ) && ( c <= '9' ) )
{
return 1 + c - '0';
}
if ( c == '_' )
{
return 1 + 10;
}
if ( ( c >= 'a' ) && ( c <= 'z' ) )
{
return 1 + 10 + 1 + ( c - 'a' );
}
if ( ( c >= 'A' ) && ( c <= 'Z' ) )
{
return 1 + 10 + 1 + ( c - 'A' );
}
return 0; // wtf?
}
uint64_t ToRadix50( std::string_view s )
{
Assert( s.size() < 12 ); // that's how many base 40 chars we can fit in 64 bits
uint64_t nRet = 0;
for( char c : s )
{
nRet = 40 * nRet + ToRadix50( c );
}
return nRet;
}
static const char s_nRadix50ToAscii[] = "?0123456789_abcdefghijklmnopqrstuvwxyz";
// Code for printing/logging with smart formatting
void ItemFormatter( Symbol_t value, char const *pFormatSpec, IOutputBuffer *pOut )
{
uint64_t nValue = uint64_t( value );
if ( ! nValue )
{
pOut->PutS( "NIL" );
}
else
{
char sBuf[14];
sBuf[13] = 0;
char *pBuf = sBuf + 13;
while( nValue )
{
*( --pBuf ) = s_nRadix50ToAscii[nValue % 40];
nValue /= 40;
}
*(--pBuf ) = '$'; // our symbol indicator
pOut->PutS( pBuf );
}
}
Why do you call this “radix 50” when it is actually base 40?
Way back in my early programming days I did a lot of coding on a Dec PDP 11/70 minicomputer running RSTS/E, on a printing terminal. In order to save precious memory and insanely expensive disk space, the OS used a string encoding with a 40 character dictionary for many OS objects, such as filenames, usernames, etc, allowing a 33% saving in terms of bytes vs storing the full 8 bit ascii encoding. This was called radix50. The “50” is octal for the decimal value 40.
What prefix to use?
In order to make symbols stand out, I took advantage of a feature of modern c++ compilers: The major c++ compilers (GCC, MSVC, and Clang) will all accept the non-standard little-used extension of allowing “$” as a component of c++ identifiers. I take advantage of this by treating such identifiers as symbols. This makes the easy to highlight in the IDE, easy to identify in the preprocess, and makes them seem like part of the language. This is optional, and if my code ever ran into problems with it because of some compiler environment unhappy with symbols that start with a ‘$’, I could simply globally replace the $ signs with some prefix such as SYM_:
// Example symbol uses
pMyObject->SetAttr( $Strength, 5 ); // set in dynamic attributes for object
Log( "%d", pMyObject->GetAttr( $Strength ) );
void ProcessOperation( Symbol_t nCmd )
{
switch( nCmd )
{
case $quit:
ExitProgram();
break;
case $save:
SaveState();
break;
default:
Log( "unknown command %s", nCmd ); // type-safe printf, Logs as ascii, not the hex value
}
}
Results:
My final solution has all of the properties I wanted, with the only drawback being the need to throw a preprocessing scanner into your build process. However, once you have done this, you can use such a scanner for multiple purposes, including generating introspection data.
Symbols are stored as simple efficient 64-bit integer enums which can be passed and returned by value.
Symbols are strongly typed
Symbol references are easily recognized in the code and can be syntax-highlighted
Symbol names can use intelligent auto-completion
Symbol references do not have to go through a long compile-time code execution component
Symbol names can be used in places other representations cannot, such as case labels and template arguments.
Symbol values are deterministic and fixed for a given name
Symbol numeric values can be mapped back to strings for debugging or serialization.
There are many reserved values which can be used for special purposes
Symbols do not have to be defined all in one place but can be part of libraries
Symbol names can be converted to numeric values at runtime without a dictionary lookup or a need for code to use them explicitly.
I’ve had some programming language design ideas rattling around for a while. Since I had an unexpected Saturday with no plans I decided to implement something I could play with. I have implemented various compilers and interpreters before, and I really wanted to be able to sprint towards being able to use the custom language to write itself. So, I wanted the fastest bootstrap process I could get. I decided that I could write a version 0 that would be thrown (or evolved) away. It would barely be a parser but enough to start using and iterating on the language syntax. This is throwaway code. Its mix of regexprs + simple string parsing logic is not sufficient to fully parse and implement a language of any complexity. It is meant as a bridge to a real parser/processor. It is however illustrative of how little code it can take to bootstrap version 0.0001 of a programming language though.
Targeting C++
One decision was to target c++ as the output of the “compiler”, instead of directly generating machine code or an intermediate representation such as LLVM. My “assembly language” output is C++. Many of my gripes about C++ can be solved by a preprocessor. C++’s semantics are powerful enough to implement almost any programming paradigm, with syntax being the only ugliness. For instance, supposed you added S-expressions with GC to C++. You would have no problem writing a C++ library implementing memory management, parsing, output, and manipulations. But you wouldn’t be able to make it read as simple as LISP. But with a preprocessor you can. The same applies to implementing things such as memory safety, etc. Other advantages are:
The compiler and its output is instantly portable to any system with a c++ compiler.
Any C++ library can be used directly. For instance, I would like to include linear algebra syntax. To do this, all I have to do is generate code for a library such as Eigen.
You can mix code in the new language with C++ just by linking it in.
Assuming the C++ code generated is nice and readable, you can use it in any project for real.
You get address sanitizer
You get good debugging from day 1. You can even use things like Live++ and edit-and-continue.
You can allow direct insertion of c++ code into your language.
But, most importantly for hitting the ground running, you can start with a “compiler” which barely understands the language but generates working C++ code, and then incrementally move from there to a real parser/code generator. My parser is just regexs plus c++ code.
Initial quick and dirty features
I’m not going into all the (somewhat contradictory) goals of this language, but will describe what I got going first. For now, I’m calling it “cgfront” (for “Chris Green frontend”), in the tradition of cppfront.
Whitespace doesn’t matter but ends of lines do. Statements are terminated by end of line, not semicolons. Multiline statements may use the “\” continuation character but generally will not have to as any unclosed braces or trailing operators (including “,”) will implicitly continue the line.
Unlike C++, parentheses are not needed around the operands to statements such as “for”, “if”, etc.
Block statements such as “if” automatically open a block. No { is needed. The block is terminated with “end” or “;” There is no need for a trailing “end” on a global definition such as “func”
CGFRONT makes a distinction between functions and procedures (functions with no return value). A procedure can be called without putting it’s arguments in parentheses: Print x // generates Print(x); in c++ output
Get rid of forward declarations. There is no need to forward declare anything or declare your functions in any order. CGFRONT outputs a header file that declares everything.
Define as much of the language as possible in the module definition. A CGFRONT library can not only add new functions and classes but new syntax.
Multithreaded parsing and compilation. The language elements were designed so that the compiler can quickly break things apart into individual statements and functions and parse/compile all of them at once.
Quick prototyping
I got enough code written and debugged in an afternoon to make the language largely self-hosted. This included:
Getting it started in c++
As soon as it could do anything, mutating the c++ code to the modified CGFRONT code. This was multiple steps as features started working.
Setting up CMAKE to run the parser when building the parser using the add_custom_command cmd to set up a pre-build step.
Keeping a “_stable” version of CGFRONT around for building CGFRONT itself. Self-hosted compilers are prone to crazy problems when bugs are introduced that prevent using the compiler to compile the bug fix. This is especially painful when you are working on multiple OSs. I build for linux and windows but generally work on them separately. So there’s the danger of checking in changes that one OS has no way to build because it does not have a stable compiler binary of the right version.
Making a quick emacs highlighting mode for the new language. All I did so far was highlight keywords, strings, and comments
Make a “module definition file” driving the compilation. This file consists of preprocessor-type directives.
Code
The code I’m posting here relies a little bit on my personal libraries (and third party code such as intel tbb). Its not meant for others to build, but is just an example.
This is all the c++ code. The only non-trivial function is ProcessFile which handles splitting the file contents into lines and then queuing the lines as thread jobs for generating the c++ output. This function is somewhat lengthy because it has to detection of implicit line continuation. To do this, it needs to retain a stack of all open brace-type tokens and also needs to know if the last operator on the line implies continuation. The definitions of both the braces and operators come via a config file.
#include "codebase/application.h"
#include "codebase/all.h"
#include "codebase/filesystem.h"
#include "codebase/strings.h"
#include "tbb/tbb.h"
#include "tbb/flow_graph.h"
#include "codebase/tokentable.h"
#include <string>
using namespace std::string_literals;
using namespace std::literals;
CStringOption s_outputFileName( "output", "output filename", "module.h" );
CBoolOption s_bMultithreaded( "multithreaded", "multithread compile" );
struct TokenDef_t
{
std::string m_matchText;
int m_nCloses = -1; // if this is a close this will be the index of the opener in m_braceDefinitions
bool m_bCausesContinuation = false; // if set, this neier opens or closes
};
struct MacroDef_t
{
std::regex m_matchText;
std::string m_replacement;
};
class CInputLine
{
public:
CInputLine( std::string && text )
: m_originalText( std::move( text ) )
{}
std::string m_originalText;
std::string m_commentText;
std::string m_output;
CInputLine *m_pNext = nullptr;
};
class CProcessor;
class FileInfo_t
{
friend CProcessor;
FileInfo_t( CProcessor *pParser, std::string const &fileName )
{
m_pParser = pParser;
m_fileName = fileName;
}
void WriteOuput( CFileHandle *outputFile );
CProcessor *m_pParser;
std::string m_fileName;
int m_nFileIndex; //< Index into the parsed file list
CIntrusiveList<CInputLine, true> m_pLines;
};
class CProcessor
{
public:
//: Init and shutdown:
template<typename ...optionTypes_t>
CProcessor( optionTypes_t... options );
~CProcessor();
//: File processing:
void QueueFile( std::string const &fileName );
//< Start reading a file.
void Finish();
//< Wait for parsing to complete and write output.
//: Options:
protected:
void ProcessFile( std::string const &fileName );
void ProcessLine( FileInfo_t *pFileInfo, CInputLine *pLine );
void ProcessModuleConfig( char const *pConfigFilename );
void PostModuleConfig();
//< All module config has finished, handle any cleanup
//: File status array:
std::shared_mutex m_fileListMutex;
CVector<FileInfo_t *> m_files;
//< Info for all files parsed or being parsed
//: Parsing tables:
CVector<TokenDef_t> m_braceDefinitions;
CVector<int> m_sortedBraceDefinitions[256]; // indexed by first char, sorted longest to shortest
CVector<MacroDef_t> m_macroDefintions; // "replace-regxp" style macros
//: Graph and nodes for file processing:
tbb::flow::graph m_fileParsingGraph;
//< This graph contains the nodes which are built to parallelize the parsing. Calling
//< wait_for_all on this graph will block until all queued files have been fully processed.
tbb::flow::function_node<std::string, int > m_fileProcessingNode;
//< This reads the lines in a file and then passes them on for parallel parsing
tbb::flow::function_node<std::tuple<CInputLine *, FileInfo_t *>, int> m_lineProcessingNode;
//< Fed lines in parallel for preprocessor substituion and tokenization
};
#include "cgfront_module.h"
template<typename ...optionTypes_t>
CProcessor::CProcessor( optionTypes_t... options )
: m_fileProcessingNode( m_fileParsingGraph, tbb::flow::unlimited, [this]( std::string fileName )
{
ProcessFile( fileName );
return 0;
} ),
m_lineProcessingNode( m_fileParsingGraph, tbb::flow::unlimited,
[this]( std::tuple<CInputLine *, FileInfo_t *> args )
{
auto [lineIn, pFileInfo] = args;
ProcessLine( pFileInfo, lineIn );
return 0;
} )
{
( SetOption( options), ...);
// Open module config file
if ( FileSystem()->FileExists( "module.cfg" ) )
{
ProcessModuleConfig( "module.cfg" );
}
PostModuleConfig();
}
CProcessor::~CProcessor()
{
m_fileParsingGraph.wait_for_all();
}
void CProcessor::ProcessFile( std::string const &fileName )
{
CFileHandle *pHandle = FileSystem()->OpenForInput( fileName.c_str() );
if ( ! pHandle )
{
Log( "failed to open ", fileName );
return;
}
FileInfo_t *pFileInfo = new FileInfo_t( this, fileName );
pFileInfo->m_fileName = fileName;
with_lock( m_fileListMutex )
{
pFileInfo->m_nFileIndex = m_files.Count();
m_files.push_back( pFileInfo );
}
constexpr int nMaxCharsPerLine = 8192;
std::string lineBuffer; // The possible multi-line buffer we will build up
std::string commentBuffer; // accumulates end of line comments
//: Context vars for handling detecting continued lines:
bool bActiveContinuation = false; // was the last token something that implies a continued line?
CVector<int> unclosedBraceStack;
unclosedBraceStack.reserve( 32 );
for(;;)
{
if ( FileSystem()->IsEOF( pHandle ) )
{
if ( lineBuffer.size() )
{
Log( "unterminated line %s stack=%? bActiveContinuation=%?", lineBuffer, unclosedBraceStack, bActiveContinuation );
}
break;
}
char inputLine[nMaxCharsPerLine]; // temp buff to read a line into
int nNumRead = FileSystem()->ReadLine( inputLine, pHandle );
std::string_view newLine( inputLine, nNumRead );
// kill end of line chars
while( newLine.size() && ( ( newLine.back() == '\n' ) || ( newLine.back() == '\r' ) ) )
{
newLine.remove_suffix( 1 );
}
// Now, we will append chars from newLine to lineBuffer, keeping track of if continuation is needed
// make some room in lineBuffer
lineBuffer.reserve( lineBuffer.size() + newLine.size() );
while( newLine.size() )
{
// eat comments
if ( CRegExMatcher _( "^\\s*//.*$", newLine ); _ )
{
commentBuffer += _[0];
newLine.remove_prefix( _[0].length() );
break; // that's the end of this line
}
if ( newLine.front() == '"' )
{
// handle string literals
lineBuffer += '"';
newLine.remove_prefix( 1 );
bool bCompleted = false;
while( newLine.size() )
{
char nChar = newLine.front();
lineBuffer += nChar;
newLine.remove_prefix( 1 );
if ( nChar == '"' ) // terminator?
{
bCompleted = true;
break;
}
if ( ( nChar == '\\' ) && newLine.size() ) // handle escaped double quote
{
lineBuffer += newLine.front();
newLine.remove_prefix( 1 );
}
}
if ( ! bCompleted )
{
Fail( "unterminated string literal" );
}
bActiveContinuation = false;
continue; // process next token/char
}
bool bDidMatchToken = false;
// Check open/close brace definition list
int nIndex = ( newLine.front() & 0xff );
for( int nCheck : m_sortedBraceDefinitions[nIndex] )
{
TokenDef_t const &def = m_braceDefinitions[nCheck];
if ( newLine.starts_with( def.m_matchText ) )
{
bDidMatchToken = true;
lineBuffer += def.m_matchText;
newLine.remove_prefix( def.m_matchText.size() );
if ( def.m_bCausesContinuation )
{
bActiveContinuation = true;
}
else
{
bActiveContinuation = false;
if ( def.m_nCloses != -1 )
{
if ( unclosedBraceStack.empty() || ( unclosedBraceStack.back() != def.m_nCloses ) )
{
Fail( "unmatched closer %s looking for opener %s ", def.m_matchText, m_braceDefinitions[def.m_nCloses].m_matchText );
}
else
{
unclosedBraceStack.pop_back();
}
}
else
{
// it's an opener
unclosedBraceStack.push_back( nCheck );
}
}
break; // no need to look at any more token defs
}
}
if ( bDidMatchToken )
continue;
// no match? just copy the character and cancel any continution (unless this is white space)
char nChar = newLine.front();
lineBuffer += newLine.front();
newLine.remove_prefix( 1 );
if ( ( nChar != ' ' ) && ( nChar != '\t' ) )
{
bActiveContinuation = false;
}
}
// we may have a line to process
if ( ( unclosedBraceStack.Count() == 0 ) && ( ! bActiveContinuation ) )
{
//Log( "got line *%s*", lineBuffer );
CInputLine *pNewLine = new CInputLine( std::move( lineBuffer ) );
pNewLine->m_commentText = std::move( commentBuffer );
pFileInfo->m_pLines.push_back( pNewLine );
if ( s_bMultithreaded )
{
m_lineProcessingNode.try_put( std::tuple( pNewLine, pFileInfo ) );
}
else
{
ProcessLine( pFileInfo, pNewLine ); // for easier debugging
}
}
}
}
void CProcessor::PostModuleConfig()
{
// We will build out the list of operators indexed by first char and sorted from longest to shortest
for( int i = 0; i < m_braceDefinitions.Count(); i++ )
{
int nIndex = ( m_braceDefinitions[i].m_matchText.front() & 0xff );
m_sortedBraceDefinitions[nIndex].push_back( i );
}
// now, sort longest to shortest
for( int i = 0; i <CountOf( m_sortedBraceDefinitions ); i++ )
{
if ( m_sortedBraceDefinitions[i].Count() )
{
ranges::sort( m_sortedBraceDefinitions[i], [this]( int a, int b )
{
return ( m_braceDefinitions[b].m_matchText.size() < m_braceDefinitions[a].m_matchText.size() );
} );
}
}
}
The self-hosted parts of the translator.
As soon as the code was barely working, I hand-translated a bunch of the c++ code to the new language. You can see a few features here, mainly the removal of a lot of semicolons and parens, the “for x in 0..10” syntax, etc.
The rest of the “implementation” is in this configuration file, which defines operators, brackets, and regex replacements (my “fancy” version of #define). The ‘@’s are a syntactic structure which prevents further substitution and defined literal c++ output code. Even though regex replaces aren’t good enough to implement even simple syntax, they can be used to prototype new syntaxes.
// define open/close brackets
#openclose ( )
#openclose [ ]
#openclose ï½¢ ï½£
#openclose { }
// define tokens that cause lines to continue if they are at the end. Generally these are binary or unary operators
#continuer ,
#continuer +
#continuer \
#continuer -
#continuer /
#continuer |
#continuer &
#continuer %
#replace "Ɐ" "for"
#replace "∈" ":"
#replace " in " " : "
#replace "^\s*func\s+(.+)$" "@auto $1 {"
#replace "^\s*proc\s+(.+)$" "@void $1 {"
#replace "^(\s*);\s*" "$1@}"
#replace "^(\s*)end\s*" "$1@}"
#replace "^(\s*)if(\s+.*)" "$1@if ($2 ) {"
#replace "^(\s*)for\s+([a-zA-Z_][a-zA-Z0-9_]*)\s*:\s*(.+)\.\.\.(.+)\s*$" "$1@for( int $2 = $3; $2 < $4; $2++ ) {"
#replace "^(\s*)(with_lock|for|while)\s+(.*)" "$1@$2( $3 ) {"
#replace "^(\s*)(with_lock|for|while)\((.*)" "$1@$2($3 {"
#replace "^(\s*)else\s*$" "$1@} else {"
This article benchmarks a few different implementation possibilities for this pattern:
There are a large number of units of parallel work to be done
Each work item may spawn more work items, so the work set changes during execution, and worker threads not only pull from the work queue but also push to it.
I use Intel TBB on both Windows and Linux, but also have lots of my own thread code to draw on. This experiment was spurred by some numeric code I was working on. It uses the simplest TBB idiom to solve this problem, a TBB task graph with a single queueing function_node. This works fine, and is performant. However, I came to the realization that I could greatly simplify my SIMD path (which operates on 8/16 work items at a time) if I could just dequeue more than one item at once from the work queue. Given that the TBB function_node is based on calling a function for each item pushed, as opposed to functions explicitly pulling items from a queue, this doesn’t really fit that model. However, one of the third party libraries I have in my codebase, the lock-free moodycamel concurrent queue (https://github.com/cameron314/concurrentqueue) developed by Cameron, is unique in that it has a fast function for enqueing and dequeueing multiple items at once.
However, before switching to this, I wanted to make sure I wouldn’t be giving up any perf from the function_node-based implementation, due to things like losing the work-stealing nature of the TBB scheduler, or perhaps faster paths in Intel’s code. So I implemented a simple test case to measure queuing/ dispatch overhead in a simple test and measured on multiple systems.
This code executes work units from a queue until a target # of units have been processed and times the execution. The queue starts out with one work unit in it, and each work unit queues a small random number of additional work units when it is executed. Each work unit just makes N calls to a thread-local random number generator and returns the result. The goal is to profile this for small values of N in order to measure the overhead of the queueing and scheduling. As N gets larger, that overhead ceases to matter, and linear parallel speedups should be attained. However, when doing parallel computations, a smaller effective work unit size provides larger scalability, so this overhead matters.
The code
We’ll start off with a bunch of command line options plus the dummy function that does the useless work of generating random numbers. We’ll include the sciplot (https://sciplot.github.io/index.html ) library so that we can easily output graphs:
Next, the very simple TBB function_node based implementation:
Now, the moodycamel::ConcurrentQueue implementation. This is more complex, especially the termination logic. We take advantage of two moodycamel optimizations here – the ability to have per thread producer and consumer tokens to reduce overhead a little, and the ability to insert more than one record at once. This templated function is used to produce two implementations, one using ConcurrentQueue and polling (which will waste cpu time spinning when there is no work to do as opposed to putting the thread to sleep), and a blocking method in which threads will go to sleep when there is no data to pull:
Since Intel TBB also has a non-blocking and blocking concurrent queue, we will also include these in the test:
Now, we’ll put those all together in a function to call them and measure+plot out the timing results:
Results and analysis
In all of the subsequent graphs, the Y axis is the execution time (lower=better), and the X axis is the number of concurrent threads used. Sorry for being unclear, I just started having my test programs output sciplot images. I’ll put axis labels in next time.
“Pure overhead” (no work per job except for queueing and dequeueing) timing on a 32-core AMD windows machine. 100,000 work items:
The bottom line:
The general overhead is low, with the difference between the fastest and slowest times on the order of 130ms (or 1.3µs per item). The simplicity of the tbb::flow::function_node implemntation may argue for its use except in cases where an explicit queue is a better expression of your algorithm (or the bulk push/pop functionality of moodycamel::ConcurrentQueue are desired).
All explicit-queue implementations are significantly faster. This is presumably because
The function_node is doing a lot more – its a component of a whole node-based task system with lots of useful functionality and options.
The function_node has to keep invoking the processing function as an indirect callback, setting up a stack frame, reallocating local variables on the stack, etc, while the queue-based implementation is just in a tight loop in one callstack.
A really big difference between the queue-based approaches and function_node is that, when there is no work in the queue, worker threads will either go to sleep or go into a polling loop. But with the TBB function_node, the worker threads are free to execute unrelated TBB tasks such as other function_nodes or tbb parallel ‘for’ loops. This can be a big deal in an application with a lot of unrelated parallel components.
The function_node’s overhead actually falls with a higher number of threads, presumably because of the work stealing algorithm keeping item data in the local L1 as opposed to everyone talking through one global queue.
Linux cost of the function_node is higher and much more spiky on similar hardware.
The intel concurrent queue’s overhead gets worse with increasing thread counts but then heads downward again past 32 (when it starts using hyperthreads).
Moodycamel is always fast, and the curve is relatively flat (slightly improving) with higher thread counts.
NOTE: This graph is showing the results for not doing any computation. The fact that execution time increases with thread count, or does not improve very much with higher thread count does not mean code using this won’t scale. Normally you would be doing jobs which consist of data processing and math. Measuring only the performance of job dispatch means that you are mainly executing various atomic instructions with low scalability. As the amount of computation done per work item increases, all of these implementations converge to the same performance.
Full results:
AMD 32 core, Windows:
Xeon 44 core dual-socket, Windows:
Xeon 48 core dual-socket, linux (AWS c5.metal, Ubuntu 20.04)
Xeon 64 core dual-socket, linux (AWS m6id.metal, Ubuntu 20.04):
AMD 96-core dual socket, linux (AWS c6a.metal, Ubuntu 20.04):
(note the different scale used in this graph)
Intel 16-core, linux (AWS c6i.8xlarge, Ubuntu 20.04):
UPDATE: Added “Rigtorp” MPMCQueue to the test
I had heard good things about this fixed-size queue (https://github.com/rigtorp/MPMCQueue). Test is on a 32 core AMD. However it doesn’t perform particularly well on this test. The test was performed in blocking mode, with a queue allocated large enough to hold all the jobs.
C++11 added both standardized support for simple mutexes (std::mutex) and read/write mutexes (std::shared_mutex). My benchmarks have shown them competitive performance-wise with both Intel TBB’s mutex implementations, and also pthread’s mutexes (which presumably the std:: ones are built upon) under linux, though which one wins is dependent upon usage pattern and whether or not a spin lock is acceptable.
Also added to the STL was std::lock_guard, an object whose job is to obtain a lock on a mutex during construction, and to unlock it when destructed. This simplifies lock management, and prevents several possible bug patterns with mutex use, especially in functions or blocks which might have multiple exit points that require unlocking the mutex:
Clearly, the second pattern is both terser and less likely to lead to bugs from forgetting to release the lock.
However, there are a couple of small nits I have with it:
The scope of the code in which the lock is held doesn’t stand out syntactically.
You have to declare a variable, which you will never reference, to hold the lock
Since the lock is tied to the same scope as all other local variables in the same block, you may end up having to add extra {} scope blocks in order to change the lock lifetime.
You would have to customize std::lock_guard to support other lock types
It ties the notion of locking to a specific mutex, when maybe you’d like the notion of how an object is locked be part of the class, when maybe you woudl like to change your locking structure for a class without needing to change the code that uses it
Since I write lots of threaded code, I made my own slightly higher level version of this, which I really like both from a readability and functionality standpoint. Via a couple of macros and template functions, I make a couple of new constructs that provide locking functions that look more like they were part of the c++ language.
I will first show examples of using the functionality, followed by the implementation. I use std::shared_mutex for these examples, but they also work for std::mutex:
You can see here that the scope of the lock becomes more obvious, and since it doesn’t explicitly reference std:: mutex classes, the underlying mutex implementation can be changed without changing the users of it.
In addition, in order to abstract away the notion of what mutex protects an object or variable, these allow locking any object (using c++20 concepts), as long as it either has an m_mutex member, or a GetLock() method that returns a reference to one:
Hopefully these usage examples are clear. So, how do these macros work?
The key thing is to take advantage of a c++17 feature – the ability to declare variables inside of an if() statement that will exist for the scope of the if. This allows inserting a variable declared outside of the {} scope into it via introducting the scope with an if. The macros are defined thusly:
Each of these macros relies on the existence of a function GetLockForObject, which maps the argument to the mutex to lock:
That’s all there is to it. I use these macros for basically all mutex operations in my codebase.
Here is paste-able code for the header file:
//:Mutex helper macros:
#define with_lock( object ) if ( std::unique_lock lk##__LINE__( GetLockForObject( object ) ) ; true )
//< Execute the following block or statement while holding the lock
#define with_shared_lock( object ) if ( std::shared_lock lk##__LINE__( GetLockForObject( object ) ); true )
//< Like with_lock() but gets a sharable lock
#define if_lock( object ) if ( std::unique_lock lk##__LINE__( GetLockForObject( object ), std::try_to_lock ); lk##__LINE__.owns_lock() )
//< Try to get the mutex and execute the body after the if_lock if successful. You can folow this with an else clause
//:Helpers for the locking macros:
inline std::shared_mutex &GetLockForObject( std::shared_mutex &mutex )
//<The lock object for a mutex is the mutex itself
{
return mutex;
}
inline std::mutex &GetLockForObject( std::mutex &mutex )
//<The lock object for a shared mutex is the mutex itself
{
return mutex;
}
template<class T>
concept HasGetLockMethod = requires( T const &obj )
//< Check if a class has a GetLock() method
{
obj.GetLock();
};
template<class T>
inline auto &GetLockForObject( T const &obj )
{
if constexpr ( HasGetLockMethod<T> )
{
return obj.GetLock();
}
else
{
// If it's not a mutex, and doesn't have a GetLock() method,
// use a member var mutex
return obj.m_mutex;
}
}
A common scenario in large-scale C++ development is having top-level classes (or functions) which expose rich API interfaces with a lot of settable parameters and options. These aren’t your lowest level classes but are the “crowns” that you have built out of them. For example, you might have a 3d rendering engine object, which supports multiple graphics APIs and has a large set of options for instantiating it, including such things as API choice, window settings, configuration parameters such as buffer sizes, file paths, VR options, selection of lighting models, optimization settings, etc. Many of these settings may need to be specified at initialization/construction time.
In my codebase, examples of this are the aforementioned rendering interface, my “Client3D” class ( which encapsulates rendering, user input, and camera motion), my “NoMPI” system (a class for distributed processing), and a suite of numeric optimizers.
Given such classes, what is a good way for the users of these systems to supply options, if there are a lot of them (for some definition of “a lot” )??
I will use my numeric optimizer classes as an example. They consist of a generic base-class and a set of derived classes implementing different optimizers. The base class is CBlackboxOptimizer, and two of the derived classes are CMatrixAdaptionOptimizer, which implements multiple algorithms in the CMA-ES family (https://en.wikipedia.org/wiki/CMA-ES) and CEvolutionaryOptimizer, which implements multiple population-based optimization algorithms, primarily variants of differential evolution (https://en.wikipedia.org/wiki/Differential_evolution).
There are a number of options shared among all 3 of these classes, as well as ones specific to each one. All of these options have defaults and so their specification is optional to the caller. They are generally supplied to the constructor, though some can be changed after that.
There are several ways to approach this. I go through a few options and then describe my system.
NOTE: I’m sorry about the variation in font readability between the code examples. I haven’t used wordpress much for writing coding articles, and it is messing up my screen grabs. I intend to bypass this by switching to a static html site and using my editors ability to export formatted code as HTML.
Using default parameter values
One way to implement this interface is via a set of optional parameters:
This has the following problems:
As the number of optional parameters increases, callers of this become unreadable lists of numeric parameters, and the error potential from using the wrong order increases:
Because c++ doesn’t let you leave out optional parameters arbitrarily, if you want to specify a default value for an optional parameter after the first one, you have to duplicate the default values in the caller!:
In derived classes you will have to compound the problem as you add more and more parameters, and cut/paste the default values from the base class:
There is no way to tell if a parameter was specified, other than comparing against the default value. If there is no good default “invalid” value, this can lead to things like using std::optional, or awkward constructs like the one used for flStartingSearchLocation above.
Any reordering of parameters in the prototype will cause trouble for the callers and potential bugs.
Using tagged parameter pairs
Clearly, most of the problems from using long lists of parameters with default come from the fact that they have to be specified in order, and that you must specify parameter values that you don’t want to if they are before the parameter that you want to override.
There are several idioms which may be used to supply parameters in the form of a list of pairs of { parameter id, parameter value}, where the parameter ID is an enum, constant, or #define:
Using initializer lists:
Advantages:
Order doesn’t matter.
You can declare the argument list as a separate static initializer list and pass it.
Problems:
You can only use this if your options/parameters can be specified as a common type such as ‘int’. But I want floats, int64_t’s, char pointers, etc.
You can pass any values at all for the option tags, with no compile-time checking that they are allowed.
If you type an odd number of values, or get your pairs out of phase, it will produce buggy code instead of a compiler error.
Using old-school varargs functions:
In this example, the constructor would walk the list of argument pairs using va_start, va_arg, and va_end.
You must terminate the argument list with some indicator such as -1 (though variadic templates can work around this).
You must be really careful to pass the right type for the option value, as _no_ conversions will be done. Passing a double accidentally by leaving off the ‘f’ suffix above would be disastrous
Messing up the phases of the pairs of typing an odd number of parameters will not be detected by the compiler, and will probably crash
There is no compiler error for passing options that are unrecognized by the constructor, and it will probably crash if you do so.
Its annoying in the debugger, since you can’t inspect the parameter values without doing a memory dump or stepping through the argument walking code.
option lists cannot be forwarded to underlying classes unless you make alternate “V” versions of the functions which take va_lists as arguments.
Using Set..() methods
Another option is to give up on the whole notion of option lists and explicitly call option setting methods for each option:
Advantages:
Order is unimportant
Any types may be used for options, and conversion operators will be invoked if needed
Easy to document the options
Handles changing options post-construction easily
The compiler will validate that option types are allowed.
Handles derived classes straightforwardly
Disadvantages:
Can be longwinded on the calling side.
If there are options that can only be set at init time (such as choosing between vulkan and d3d for a graphics renderder), construction and init will have to be separated in order to give you a chance to Set the option.
Doesn’t provide an easy compiler-enforced way to separate options which are allowed post-init vs pre-init.
My method – using variadic templates plus strong typing
The method I have been using of late overcomes most of the negatives of other methods while being versatile and encouraging very readable code.
What I do is define a small one-line struct for each optional parameter, and take advantage of various modern c++ features to make it work well.
First off, in order to be able to use short succinct names for these types and to have a common convention for them, I use a namespace, ‘opt:’ for all of these utility types. Any class or function which wishes to use this idiom can simply add definitions to ‘opt’. Using a namespace (or using only one namespace) is not required, but is the convention I have chosen. The repeated use of the generic field name m_value is intentional to simplify template code.
I then define the constructor as a variadic template:
For each allowed option, I define a SetOption function. Note that my coding style doesn’t normally allow one-line definitions like this, but I make an exception when I think it improves readability of the header.
I then implement the constructor so that it calls the appropriate SetOption() function once for each optional argument supplied. The secret sauce here is to use the terrible c++ “fold expression” syntax to do one method call for each variadic template parameter:
And invoke it as so:
Advantages:
Order does not matter
Passing an option unsupported by the class causes a compiler error.
Type promotion is done automatically
Produced code is extremely efficient, including inlining.
Debugger breakpoints can be set on specific options via putting a breakpoint on SetOption.
Option lists can be forwarded to other functions or classes via passing a parameter pack. This is extremely useful, for instance, if instead of directly instantiating the CBlackboxOptimizer, you wanted to have a “CreateOptimizer()” function which created one and passed an option list to the constructor.
Verbose names can be used to describe the options
Enum options do not need to be wrapped by a class (note the OPTIMIZE_FIND_MAXIMUM above)
Options can be in base classes. If CBlackboxOptimizer was a subclass of CGenericOptimizer, which implemented some of the options, all that needs to be done is to add “using CGenericOptimizer::SetOption;” to the CBlackboxOptimizer class.
An option can contain logic in its constructor, or multiple constructors.
It is easy to separate the notion of whether an option was unspecified, or was specified as a default value.
Options can be used without values just by defining empty structs.
Options can inherit from other options
Options can be typedef’d to provide aliases.
You can easily separate options which can be changed after initialization from those which cannot, by using ‘private:’ or ‘protected:’ in the definition of the SetOption() methods.
SetOption() calls themselves can be templates, in order to group processing of multiple similar options together. You can use “if constexpr” to compare types, c++20 “requires” expressions, etc.
Disadvantages:
Code for a constructor will be generated for each subset (and ordering) of options used. However, these can be very small.
I have an application that involves voxellizing meshes into a large 3d array of floats and then performing image-processing type operations on the resultant 3d array of floats.
I do this on systems with a lot of cores (44, 48, and 128) and a lot of memory, so these operations run really fast, even including things like generating distance fields on large arrays. 2K x 2K x 2K is plenty fast to process, even though it is 32 gigabytes of RAM.
When doing some benchmarking of this code on a new system, I noticed that despite all of my code being heavily multithreaded, on really large problem sizes, it would spend a huge amount of time at the beginning (many seconds) with the process manager only showing one core in use. My compile-run cycle was being dominated by this. 7 seconds to compile, 3 seconds to run the algorithm I was working on, plus 10 seconds of mysterious start up time!
So I investigated with the debugger:
I first tried building a debug version even though I knew it would probably be too slow to be practical working on 32GB arrays. I hit F5 and waited a bit until it was churning away on the startup delay. I broke in the debugger. It was not in my code, but rather in a not-so-well coded memory filling loop in the debug memory allocator that was scrubbing my 32GB voxel array. I cursed that – my filling of the array takes nowhere near that time, and uses multiple threads doing non-caching stores to avoid trashing the cache. I decided I’d debug the release build instead. In retrospect, I should have been suspicious though, since even a byte-at-a-time single threaded loop should be able to fill this memory in a second or two.
So I broke into the running release version during the slow part. It was actually in a big loop in my binary this time. It was iterating over a large block of memory, writing one byte of ‘0’ every 16 bytes. This was compiler generated code for operator new[], executing a constructor on a huge array. But the class was just a plain 16-byte struct with no constructors (or so I thought), that I later initted via threaded code.
The struct being setup was a block of scheduled operations with dependencies, that would then be used to execute the math on 128 cores. When fed a large problem and a lot of CPUs to break it up into, this could also be between 16GB and 32GB. No worries, I’ve got 256GB of RAM, and enough CPU power to write 16GB of data in way less than a second. But why was the compiler code executing a constructor on it?
Well, it turns out that std::atomic_int8_t, unlike an ordinary uint8_t, has a constructor that sets it to zero. I had thought of them as just an int that supported the locked operations, but they also had this property. In my case, I wasn’t happy about this – I already init them much faster, using multiple threads, and 0 isn’t the value I set them to.
My options were either to just use int8_t instead of atomic_int8_t, and use casting when I needed to do the actual atomic decrement. Or I could allocate them as an array of uint8_t’s and cast the result to WorkItem_t *. I made a generic version of this:
I put a benchmark timer around the new[] call for WorkItem_t, and bypassing the constructor reduced the time from 25 seconds to basically zero. Problem solved! (?)
I was also annoyed that not only was it doing a constructor that I didn’t need, but it was executing it on one thread on 32GB of memory, even though I had 256 HW threads. What if I actually needed the constructor? What if the constructor was expensive? I certainly would want the init to use all my cores. So I added this definition:
Now that I had that, I dropped my code into a little test benchmark program that timed different ways of allocating and initializing 32GB worth of this struct. My tests were run on two systems:
System A: Windows, dual socket AMD Epyc 3rd generation system. 128 cores, 256 HW threads, 256GB of RAM with high memory bandwidth via fully populating all the NUMA lands.
System B: Linux, AWS EC2 dual Xeon system with 48 cores, 96 threads, and 192GB of RAM.
/list
The results were:
plain old operator new[]: A: 28s, B:13.55
FastNew (threaded constructors) : A: 10, B:2.79
I also decided to try bypassing the constructor, and use memset to subsequently fill the array. I also wrote a parallel memset to try out as well:
This produced on both systems that were similar to the vanilla operator new[], and the parallel constructor respectively, as you would expect. So basically I could only get the startup time down to 10s (unacceptable) on windows and 2.79s on Linux (still bad).
But these numbers didn’t make any sense now that I had reduced everything to a simple memset. Even though every 4th iteration of the init loop would cause a cache miss on read and an eventual writeback (because I don’t have 32GB of cache!), the numbers didn’t add up. Both these systems can write memory a lot faster than that. The AMD system has 8 channels of memory at >20GB/s each, and the Xeon is no slouch either. What’s going on? I thought about pathological TLB misses as well (fixing this would require using “large pages”) but that wouldn’t be enough to make it this slow either.
Ah-hah, it must be page-faulting. I have way more than 32GB of RAM, so it couldn’t be swapping. I figured that the OS must not be really allocating the memory, but allocating physical RAM when the first access to a region causes a page fault. If my data is 32Gb, and pages are 4K (or are they 8K?) in size, that would mean 8 million page faults. That certainly could add up to something!
So, I change my code to memset the newly allocated memory _twice_ instead of just once. Boom! The second (single-threaded) memset only took 2 seconds instead of 24s for the first one.
Ok, so even when I eliminate the memory initialization, I’m paying the same page fault cost later on first access. The 24s of page fault handling just gets amortized over the whole run time, but my code is threaded so its probably only added 10s or so to the runtime. But that’s on an algorithm that runs in less than 10s if the memory had already been paged in. I’m spending more time letting the OS handle page faults than I am doing math, all because the OS is acting as a very slow gatekeeper in front of my 256GB of RAM!
What I would want it to do is just allocate all the pages up front in a tight loop instead of giving them to my app one at a time in an exception handler. I looked at the docs for Windows VirtualAlloc, figuring there must be a way to do that. Nope. It explicitly states that comitted memory is assigned to DRAM pages upon first processor access, without a flag to override this :-(.
I tried VirtualAlloc over new[] anyway, since it would let me try large pages:
This didn’t provide any significant speedup over operator new[] as you would expect. The equivalent of VirtualAlloc on linux is mmap and it looked like it had some relevant flags so I threw that into the mix as well:
This, as expected yielded the same speed as operator new[], but I wanted to try out the exciting MAP_POPULATE flag, which says that it pre-populates the page table instead of relying on faulting it in. Exactly what I need! Unfortunately, adding that flag didn’t change the numbers at all. I read some things on the web that implied it was actually a NO-OP? :-(.
So the only thing left to try was “huge pages”. Normal virtual memory page sizes are either 4k or 8k. Huge pages are either 2MB or 1GB, which is a massive reduction in the number of pages required to hold my 32GB of data. On both Windows and Linux, you have to do something to enable them as they are normally disabled. In Linux it was “sysctl -w vm.nr_hugepages=N” where N was how many 2MB pages you wanted to have available. I asked for 32768, which adds up to 64GB. I added the MAP_HUGETLB flag to mmap, and it gave me 2x:
mmap + memset : 14s
mmap + huge pages: 8
mmap + parallel memset: 2.8
mmap + huge pages + parallel memset: 0.407s
I didn’t try out 1GB pages, but I’d expect them to make the OS overhead of allocating the memory approach zero.
Now what about huge pages on windows? It turns out that they are a terrible pain to enable, involving changing user permissions, rebooting, and running your app as administrator. I really want to see if it helped, so I followed instructions online for doing this, and added the proper flag to VirtualAlloc(). It didn’t work, and I didn’t feel like goggling over the web and trying to figure it out. Most of the articles on large pages in Windows were old, referring to ancient versions of the OS, pointing at dead web pages, etc.
So the bottom line if you need a huge memory array is:
To get a 35x speedup on large memory allocations in Linux, use mmap with large pages, and use threads to initially touch/fill the memory.
To get a 2.8x speedup in windows, allocate the memory without initialization and then use threads to initially touch/fill the memory.
If your application is going to fill the memory later, but you just want to pull it into the MMU tables, the right answer is probably to allocate the memory un-initted, and then spawn asynchronous jobs to walk through the memory, just performing reads in order to get the page faults to happen. You don’t have to wait for these threads to complete to start doing work. They are just asynchronous prefetchers.
So I’m let with an unavoidable 10s of startup time on a 128 core Windows box. Can anyone demonstrate allocating a 32GB array and filling it in in < 10s on Windows?
In my application, I need to find interactions between curves defined over time. In particular, I need to be able to find the time at which 2 curves come within a certain distance of each other. So, given two curves in space f(t), and g(t), I wish to find the first point along t for which (dist^2( f(t),g(t))-rad^2 = 0. Solve for T. But with f(t) and g(t) as bezier curves, that’s a 6th degree polynomial equation with no closed form solution. It’s even worse when the sin’s and cosines from rotation get involved. I have isolate roots and iteratively find them.
Normal tools for this are line search, subdivision, and newton iteration. Interestingly, AVX (and especially AVX-512) really change the tradeoffs. When you can evaluate your function at 8 (or 16) different locations as cheaply as one, subdivision is a lot more effective than when you’re just evaluating at the midpoint and gaining 1 bit of accuracy per function evaluation.
Benchmarking and measuring accuracy, the best tradeoff on AVX was to do eight equally spaced evaluations. I then test the signs of these evaluation to look for a zero crossing. I then take the interval containing the zero crossing and perform 8 more evaluations along that interval. I then locate the sign crossing within the new interval and repeat the process, which gives me an accuracy of around 9 bits. Last up is 8 simultaneous Newton steps from starting points equally spaced on the interval that the last 8-way subdivision step yielded. Whichever of these results is closest to 0 is used as the function value estimate.
I needed to write a basic worker thread pool implementation. I needed a simple system that let me queue jobs, have those jobs executed by worker threads, and wait on job completion.
I looked at a few public ones, including the intel TBB library, and some fairly simple portable c++11 versions. I ended up writing my own because:
It’s not especially difficult, especially with c++11’s thread-related library functions.
I wanted to be able to iterate on it in the long run, including using the intel TSX primitives and coding a work-stealing system.
I wanted a feature which isn’t present in the libraries I looked at for assigning jobs based on NUMA nodes.
 For right now, I’d be happy with a really simple, not especially efficient one. I figured I could just grind it out almost as fast as I can type, using std::thread and c++11 synchronization primitives, and later on worry about making it lock free, managing memory, handling NUMA, etc.
The last point turned out to be true. Using std::thread, a mutex-guarded queue, and condition variables for signalling/waiting, it was really simple, and worked the first time that it compiled.
But when I started using it, there was a bit of a mystery! My development system is unusual in that it is a dual-socket Xeon system with 44 physical cores (88 logical when you count hyperthreading). This is good, as I’m writing code for the cloud that is intended to be ridiculously parallel. It’s also good for multi-threaded builds 🙂
When I started testing my thread pool with some numeric benchmarks, I noticed that I only got a roughly 30x speedup, no matter how simple the jobs were. I had previously observed the same behavior at home on the same system when I was working on threaded code at Valve. At the time I figured there must be something in the Valve libraries preventing code from creating the right number of threads or that it was doing something unexpected with processor affinity. I also thought that the less-than-linear scaling could be clock-throttling as all the idle processors start heating up. But then, after seeing the exact same thing from my simple code, I decided to investigate….
Long story short: Until recently, Windows only supported a maximum of 64 processors. Looking at the API for affinity masks, etc, you can see why – they use a 64-bit mask to represent the processors. However, modern versions of Windows do support more than 64 cores. A bunch of googling revealed that this is done via dividing the processors into “processor groups”. These assignments are done at boot time:
Any system with 64 processors or less will end up with a single processor group (0) containing all of them.
Systems with >64 logical processors will have more than one processor group, with the assignment of the processors done by the OS at boot time. There are a set of rules for how to divide them up that are controllable by some boot parameters.
My system chose to divide them into two equal groups of 44 logical processors, with each group containing all of the processors associated with one socket/NUMA group.
When starting a process, the process is assigned a group. Windows appears to use some heuristic to decide which group. If you launch your app multiple times, sometimes it will be assigned to one group, sometimes the other.
A thread will ALWAYS run on a processor in its assigned group.
When starting a thread, if unspecified, that thread is assigned the group of the process that started it.
I first wondered why it split the processors on my machine into equal-sized groups instead of putting 64 in group 0 and the rest in group 1 (which would maximize the performance of threaded apps that don’t know about groups). The way it does it now means that most threaded apps only use half of the cores, when they could have used 64/88 of them. However, that would have resulted in two issues:
24 cores would be completely unused by apps that aren’t processor-group aware
Starting more than one threaded program would still result in idle cores. The way it works now, at least all your cores will be used by threaded apps if you start more than one of them.
Fortunately, that’s all moot, as it’s not hard to distribute worker threads across processor groups. Sadly, that means that I had to add some system-specific code for windows, so it’s still not quite possible to write a usable totally portable thread pool using c++11.
void CThreadPool::DistributeThreads( void )
{
#if OS_WINDOWS_64
//!!BUG!! need to skip this code for old windows versions
int nNumGroups = GetActiveProcessorGroupCount();
if ( nNumGroups > 1 )
{
Log( "System has %d processor groups", nNumGroups );
for(int i = 0; i < nNumGroups; i++ )
{
Log(" group %d has %d processors", i, ( int ) GetMaximumProcessorCount( i ) );
}
int nCurGroup = 0;
int nNumRemaining = GetMaximumProcessorCount( nCurGroup );
for( int i = 0; i < m_threads.size(); i ++ )
{
auto hndl = m_threads[i].native_handle();
GROUP_AFFINITY oldaffinity;
if ( GetThreadGroupAffinity( hndl, &oldaffinity ) )
{
//Log( "thread %d, old msk = %x, old grp = %llx", i, oldaffinity.Mask, oldaffinity.Group );
GROUP_AFFINITY affinity;
affinity = oldaffinity;
if ( affinity.Group != nCurGroup )
{
affinity.Group = nCurGroup;
auto bSucc = SetThreadGroupAffinity( hndl, &affinity, nullptr );
if ( ! bSucc )
{
Log( "failed to set gr aff err=%x", (int) GetLastError() );
}
else
{
//Log( "Set group for thread %d to %d", i, nCurGroup );
}
--nNumRemaining;
if ( nNumRemaining == 0 )
{
nCurGroup = min( nCurGroup + 1 , nNumGroups - 1 );
nNumRemaining = GetMaximumProcessorCount( nCurGroup );
}
}
}
}
}
#endif
}
Making this fix raised my multithreaded speedup in a simple numeric test from 30x to 64X!
This seems like a mistake in visual c++’s implementation of std::thread. These changes to the library would make simple c++ threading work on Windows machines with >64 logical processors
std::thread::hardware_concurrency() should have returned the total # of processors in all groups. Instead it returned 44 (the number of logical processors in group 0 )
creating an std::thread should keep track of the # of threads created so far and assign newly created threads to non-default processor groups when the # of threads created exceeds the # of processors in the default group. When more threads are created then the total # of processors in all groups, it can cycle back to the first group.
One of the first pieces of code that is usually required early in a project are some functions for simply printing messages and formatting program data into human-readable text form.
Generally these functions build on top of those already in the c++ library, but add more features. For instance:
Even a simple text-based program that wants to print some message to aid in debugging will want to have a version of printf() that also uses OutputDebugString (in windows) to show the output in the debugger’s output window.
The output may want to be sent to a set of listening sockets connected to dev consoles. Or it may need to be displayed in a graphical fashion in a fullscreen vr application. It’s common to output a timestamped log of output as well.
When there is a lot of output available, you may want to add filtering features.
You’ll usually have the notion of logs that only appear in the debug version of the application
Just to save typing and memory, it’s good to have a printing/logging function that adds the newline at the end for you.
There are two main methods of formatting text and data together in c++ using the standard libraries. First off, there are the original c format-string-based functions such as printf, etc. C++ added the stream-based functions which work by overriding the shift operators.
It can be very compact, especially when mixing data and string literals together in a stream
The ability to use a variable format specification can be powerful. Since the format specification is in the form of a string, it can be localized, including making format changes for different languages.
Compact code generation
Very familiar
Disadvantages of the C model
Dangerously error prone. Mismatched argument specifiers or number of arguments can cause anything from confusing results to severe crashes and security problems. While some compilers (gcc) are good at catching these errors at compile time, they can do so only for literal format strings. And even if the compiler catches it, it’s still an easy to make error that slows the programmer down to fix.
No ability to define printing operators for user-defined types, even simple ones.
Oriented around fixed-size character buffers.
In order to be able to extend functions, you have to have implementations that take a variable number of parameters, but also matching ones that accepts va_args arguments.
No auto casting. Even if a type knows how to convert itself to an int, the conversion operation won’t be invoked when you try to pass it to printf.
It complexifies printing things in template code. You won’t necessarily know what format specifier to use, and some template args may not be printable.
Advantages of the C++ model:
The use of templates and operator overloading for both the stream destination and the printing functions makes it very customizable for user data types
You can easily define your own formatting operators.
You can easily print your own datatypes
Disadvantages of the C++ model:
I don’t care for the aesthetics of its use of <<
It can be very wordy, especially for things like controlling format width, etc
Different code is generated for every combination of argument lists that you print. For printf, there’s only one function, with the formatting encoded in data.
So, thinking about all of that, I wanted to come up with a solution I was happy with, but that also didn’t involve writing a lot of code. My first idea was to just use variadic templates to wrap the cout/operator<< system with something hat didn’t use ‘<<‘, but would just map the syntax:
Print( "2+2=", 2+2, " and 3*3=", 3 * 3, endl );
This gets around the “<<” annoyance, though it is still not as terse as printf. It also has the disadvantage of not being especially familiar to users of either system. I imagine programmer’s making the mistake of trying to put “%” format specifiers in the first string argument.
With a little more reflection, I think I’ve come up with the perfect solution (for me) and implemented it. I’m using a version which is type safe and allows user-defined printing operators. It also allows you to make function which accept format strings, or to use a non-formatted function like the version of Print() above.
What I do is create a variadic template function which packages it’s arguments up into an array of small structs which know how to print themselves. A driver function then parses the printf-style format specifier string while iterating over the arguments to be printed.
For defining printing function, all that is required is the implementation of a printing function called ‘PrintFormatter” for your type.
Because it knows the types and number of arguments, it can avoid the runtime failures normally possible with printf. Instead of bad formatting specifiers producing run-time errors or bugs, we simply redefine them to produce useful results:
Specifying more format specifiers then arguments will cause the later specifiers to be ignored
Specifying fewer format specifiers than the number of the arguments causes the left over arguments to be printed using default formatting options. This allows you to leave ‘%’ specifiers out completely if desired.
Using an incorrect specifier causes the data to be printed using its default formatter.
I allow and encourage using the ‘generic’ specifier ‘%?’ or “%s”.
Because the format specification string is passed to the printing function for user-defined data types, they can use it for their own formatting options. For instance, I have a class holding a 2D integer coordinate. If you print it using “%d”, x and y are printed in decimal. If you pass “%x”, they are shown in hex.
The underlying printing code is just that built into printf. I didn’t write any numeric formatters.
Examples:
// identical usage to printf
PrintF( "2+2=%d and 3*3=%d\n", 2 + 2, 3 * 3 );
// no %d necessary
PrintF( "2+2=", 2+2 );
// print 3d vectors
v3f vPosition( 0., 0., 1000. );
PrintF( "pos=%f", vPosition); // prints as : pos=[0. 0. 1000.]
// printf std::strings with no problem
PrintF( "my string=%s", a_std_string );
Implementation:
I implemented this as a templated class to hold the argument descriptors, and a variadic template which is used to build an array on the stack of these. Once the arguments are built, it then calls a lambda which does the actual work. This lambda is different for each function that takes a format specifier (for instance, PrintF and SPrintF).
/// the base class of a print descriptor.
class IPrintDispatcher
{
public:
// need to add a definition here for each output class that can be printed to
virtual void Print( char const *pFormatSpec, CStringBufferDescriptor &out ) = 0;
virtual void Print( char const *pFormatSpec, CStdOutBufferDescriptor &out ) =0;
};
/// this template will be generated for all argument types. PrintFormatter( arg .. ) must copile for the class
template class CPrintDispatcher : public IPrintDispatcher
{
public:
T const *m_pValue; // by pointer. We don't want to copy the args
CPrintDispatcher( T const *pValue ) { m_pValue = pValue; }
virtual void Print( char const *pFormatSpec, CStringBufferDescriptor &out )
{
PrintFormatter( *m_pValue, pFormatSpec, out );
}
virtual void Print( char const *pFormatSpec, CStdOutBufferDescriptor &out )
{
PrintFormatter( *m_pValue, pFormatSpec, out );
}
};
There’s a templated class which is used to receive the output. For the case of SPrintF, this class just holds a begin/end pair representing the bounds of the output buffer. For PrintF, this class buffers nothing and just prints the characters as they are added:
I let you print an std::array. Using “%200?” for the format specifier gives it a max of 200 characters to show the array. Using just “%?” or no format specifier lets it use up to 20 characters.
template<class DTYPE, int N, class OTYPE> void PrintFormatter( std::array<dtype,n> const &data, char const *pFormatSpec, OTYPE &out )
{
char sBuf[8192];
int nMaxLen = 20;
if ( sscanf( pFormatSpec, "%d?", &nMaxLen ) != 1 )
{
nMaxLen = 20;
}
nMaxLen = max( 8, min( nMaxLen, ( int ) sizeof( sBuf ) ) );
CStringBufferDescriptor tmpOut( sBuf, nMaxLen );
out.Put( '[' );
for( int i = 0; i < N; i++ )
{
if (tmpOut.IsFull() )
{
break;
}
PrintFormatter( data[i], "%?", tmpOut );
if ( i != N - 1 )
{
tmpOut.Put( ',' );
}
}
if (tmpOut.IsFull() )
{
sBuf[nMaxLen - 1 ] = 0;
sBuf[nMaxLen - 2 ] = '.';
sBuf[nMaxLen - 3 ] = '.';
sBuf[nMaxLen - 4 ] = '.';
}
else
{
tmpOut.Terminate();
}
out.PutS( sBuf );
out.Put( ']' );
}
</dtype,n>
Any class can define a .PrintFormatter method for printing itself
/// the decltype below uses SFINAE to make this template only match classes containing a .PrintFormatter method
templateOTYPE> auto PrintFormatter( T const &pData, char const *pFormatSpec, OTYPE &out )
-> decltype( pData.PrintFormatter( pFormatSpec, out ), void() )
{
pData.PrintFormatter( pFormatSpec, out );
}
SIMD types have printing methods that check for all components being the same and show an abbreviated output for this case
SOA types show the data as AOS. For instance, my type that stores 16 3-dimensional vectors in SIMD format prints out as if it were stored as 16 vectors in AOS format.
Casual Numerics 