Monthly Archives: December 2016

Project Highlight: Voxelman

If you spend any time over at r/VoxelGameDev, you may have seen posts about Voxelman, the plugin-driven game engine MrSmith33 is developing with D. His real name is Andrey Penechko, and he started work on Voxelman after he was inspired by Minecraft to think about all the cool things he could do with a voxel engine, particularly the low-level optimization tricks he could use in implementing one. Then he jumped in and started figuring things out.

I started the project somewhere in 2011 or 2012. It began with creating an SDL window and getting some triangles on the screen. Then I did cubes, then a single chunk. It was a simple, single-threaded thing. I did it all with a fixed camera and only had rudimentary camera controls.

For that initial version of the project, he was using C++, but he found himself stuck from a lack of knowledge about the language. So he started searching to see what else was out there. That led him to D.

I don’t really remember how I found D. I was in need of some statically typed compiled language other than C++. I was frustrated about all the source file organisation, the need of forward declarations, header separation and the include system. In D, it was as simple as writing code. I bought a cheap 10 inch tablet just to read Andrei’s book, because my 3.2″ PPC was too small to read the whole thing. I enjoyed reading every single bit of it.

His ultimate goal with the project is to provide a platform for which people can create and share plugins and game worlds.

Ideally a complete project build should have the engine source and tools (launcher, source editor, compiler). Players should be able to initiate a connection to any server in the server list, then the launcher will download any missing plugins, compile a new executable and start the engine with the list of plugins. Currently, a build of Voxelman is less than 3MB in size. I think that this is a good property to have.

The major sticking point he sees with this approach is the dependency DMD has on the Microsoft tools for 64-bit (and 32-bit COFF) support on Windows (specifically the Windows SDK and the Microsoft linker). Even though the MS linker is considered the system linker, it’s not uncommon to see Cygwin and or one of the various distributions of MinGW installed instead of the MS tools. In a perfect world, he could tell people to download the D compiler and they would have everything they need. But it’s not a deal-breaker, so he’s not letting it stop him.

Voxelman uses a client-server architecture, where the server can be launched in a dedicated process or as part of the client’s. This is managed by a launcher which, in addition to launching the game, can be used to compile projects, manage the world, and find servers to connect with.

World and mesh generation is multi-threaded and, as in most such engines, the model is chunk-based. The chunk management implementation is informed by the concept of entity component systems, with a chunk’s world position serving as its entity ID and layers functioning as components.

Each dimension is broken into chunks. A chunk is a 32³ array of blocks. Each chunk can have a set of data layers (currently blocks and block entities). Each layer is essentially an immutable snapshot. It can be of different storage types (uniform, where all blocks are the same,  or a compressed or full array, where the layer stores an array of data). Those layers then can be freely transmitted between threads, with reference counting done in the main thread. When a layer is no longer needed it’s deleted.

Immutable chunk data makes for fast auto saves of chunk snapshots in a separate IO thread.

When a chunk is received on the client side, it can be sent to a worker thread and the geometry will be generated. Snapshots are sent to the IO thread when save points occur, and they can still be used in the main thread, sent to the client, or processed by other worker threads. One can easily use an old snapshot while several new ones are in use. Whenever a layer is being modified, data is copied into a write buffer, changes are made, and at a commit point at the end of the frame, all write buffers are committed to chunk storage.

Andrey calls his plugin system “semi-hackish”.

All plugins inherit from an IPlugin interface. Then, each plugin registers itself in a global table of plugins from a shared static constructor. The global table has lists for server and client plugins. The engine adds those plugins to the plugin manager based on a provided plugin pack. The plugin manager implements the initialization sequence. When starting initialization, you have lots of dependencies, so you need to run things in a specific order.

He has found a lot of things to like about D. As major pros, he cites the module system (“no forward declarations”), foreach loops (“99% of loops in my code are these guys”), associative arrays, delegates, and templates (“They’re beautiful; you simply add another set of parentheses and you’re done”). He also loves D’s dynamic arrays (slices).

They are a perfect design, with the pointer and the length bundled together. You can append to them, concatenate them, and change their length.

As minor pros, he lists D’s Compile-Time Function Execution and its code generation and compile-time introspection features. Unlike some D users, he also counts the garbage collector in that group. He has implemented a mix of GC-ed and non-GCed memory in Voxelman.

High-level stuff is fully in GC memory. I call something high-level if it has only one instance, so I use interfaces/classes for the high-level parts. Low-level things are mostly stack allocated, using structs (which are POD in D), and the most performance sensitive and memory consuming parts use manual memory management (via Mallocator). This includes chunk storage and chunk meshes.

He also has a list of rough corners. He doesn’t like that support for DLLs is not yet fully functional and reliable. He has found problems when trying to use shared (for example, the Mutex class cannot be used with it). He also finds all the use cases of the is expression confusing, saying the syntax “feels like regular expressions for templates; very powerful and concise, but hard to understand.”

His difficulties with shared actually took him down an interesting path that ultimately had a positive impact on performance.

I started my multi-threading by using the send and receive functions from std.concurrency. I found that I needed to send messages of variable length. For example, when loading or saving chunks, you need to send all the layers to another thread. This involved allocating arrays for all the layers and also required the use of shared.

This situation led me to the implementation of a lock-free message queue, where each message is just a stream of bytes. You write variables on one end and read them from the other. This is obviously a single producer, single consumer queue.

A disadvantage was the use of a fixed-size circular array. You need to make sure that the queue doesn’t fill up. This was a point where I found a good book that explains how atomics work: C++ Concurency in Action: Practical Multithreading. This is one of the places in D’s documentation where you feel a lack of pointers on where to find relevant information on a specific topic.

So the new solution doesn’t require any allocations and is actually faster than the built-in one. Later I added a notification system via Semaphore, so that worker threads wait when out of work.

If you’re looking for an open source D game to contribute to, Voxelman is waiting for you. You can read more about some of its internals on reddit, check out some images on imgur, and watch some videos on YouTube. I’ll leave you with this example of it in action:

The D Language Foundation’s Scholarship Program

d6The D Language Foundation recently announced a new scholarship program aimed at EE and CS majors attending University “Politehnica” Bucharest (UPB). I contacted Andrei Alexandrescu for a few details on how the initiative came together, hoping for just enough tidbits of backstory to craft a blog post around. He obliged in a big way, turning my one question and “a few details” into an informative conversation.

Mike: I assume quite a lot of work went into this. Could you share a few details about how it came about?

Andrei: Gladly! The story starts back in 2012, when I gave a talk at the How to Web conference in Bucharest, my native city. It was a great event and I got to meet many great people. Except for one whose name kept coming up all over the Romanian IT space, Andrei Pitis.

I heard he was an instructor in the CS department at UPB (the best IT school in Romania, also noted internationally). He’s been directly involved in a number of IT-related foundations and professional organizations, and he created and led the immensely successful Vector Smart Watch startup. So, having heard he’d be around, I went to the conference speakers’ dinner hoping to bump into him.

Not knowing what he looked like, I was just craning my neck in search of someone who seemed popular. Meanwhile, I was passing time by making chit chat with a nice fellow who introduced himself to me. Now, you know how these group parties go. There’s always loud music and conversation, so I didn’t even hear his name and assumed he hadn’t heard mine.

As the evening progressed, I figured Andrei Pitis wasn’t going to show, so I had more time to chat with that fine gentleman. And I noticed two things. First, he was incredibly insightful. Second, he seemed equally excited about meeting me as I was about meeting Andrei Pitis. After a long while, the coin dropped: they were one and the same.

Thus started a great friendship. Andrei gave me great tips about how to start and conduct The D Language Foundation. Recently, he introduced me to two UPB CS systems professors, Razvan Deaconescu and Razvan Rughinis (together, the three had created the Tech Lounge nonprofit organization dedicated to helping graduating CS students start their careers).

Razvan Rughinis came up with the scholarship idea while we were chatting over beers in the quaint old town of Bucharest. In great part the idea was motivated by the strong interest UPB systems graduate students had in participating in a high-impact open source project such as the D language as part of their MSc thesis. In systems research (unlike e.g. CS theory), actual system building is a key part of the research project; therefore, a visible OSS project makes for a much stronger dissertation than the usual throwaway experimental code.

Clearly a strong opportunity had presented itself, and the DLang UPB scholarship is its realization.

Mike: How does the selection process work?

Andrei: The two professors introduce a few candidates, which I pass through the rigors of the typical Facebook interview. We also ask for the usual suspects – proof of enrollment, transcripts, motivation letter, and references.

Of all components, the most important are (in order) the interview, the quality of the BSc projects, and the recommendation letters from their professors. The four current scholarship recipients passed the interview with flying colors and have very strong BSc projects and references. Some of them returned from summer internships at prestigious companies such as Bloomberg, others won CS awards. I have no doubt any company in the Bay Area or elsewhere would be happy to work with them. Once they finish their MSc, of course :o).

And I should mention here that the two professors aren’t only involved in the selection process. They will make themselves available to help manage the students on an ongoing basis. We’re very fortunate to have them.

Mike: Can you provide any info on the current recipients and their projects?

Andrei: The current recipients are Alexandru Razvan Caciulescu, Lucia Cojocaru, Eduard Staniloiu, and Razvan Nitu. I have posted an introduction to each on the D forums and, now that you mention it, I told them to create a wiki page with a blurb for each. They are hosted in a nice shared office kindly donated by Tech-Lounge.ro and… we’re in the process of getting a coffee machine up there :o).

They are all obviously interested in taking large systems projects that benefit their research interests and have an impact on the D language. To get them started, I took a page from Facebook’s practice and defined a “bootcamp” program. Bootcamp is a month-long process (six weeks at Facebook) during which the so-called n00bs get familiar with the technologies used in the organization: the language proper; the core runtime and standard library; the build process; the way code changes are created, reviewed, accepted, and committed; and, last but not least, the community ethos and the kind of problems we are facing that are fit for ingenious solutions.

To kickstart the bootcamp program, I defined a “bootcamp” label in our Bugzilla and applied it to a bunch of existing bugs, with an eye for the kind of bug that simultaneously has low surface (you don’t need to know a lot of internal details to get into it) and offers a good learning experience. Right now each student is busy fixing a couple of such bugs.

Long-term we are looking at high-impact libraries and tools. I do have a few ideas, but I have no doubt the students will come up with their own. Just give them time.

Mike: Speaking of time… is there any room here for an update on the D Foundation’s finances?

Andrei: Of course. To be honest, right now we’re in better shape than ever before (and than I would have hoped). Thanks to Sociomantic, who footed a large part of DConf 2016’s bills, we have quite a bit of change left from conference registration fees. I have also personally carried a number of high-profile appearances at public tech events and private corporate training events, with proceeds flowing to the Foundation.

So we have accumulated a little war chest – not much, but definitely not negligible. With our current funds and operational costs, we are covered for over two years. Of course, the situation is fluid and I am working on expanding both income and (useful) expenditures.

We’re running a very tight operation, and I want to keep it that way. By the Foundation bylaws, its officers (Walter Bright, Ali Çehreli, and myself) cannot get income from the Foundation, which preempts a variety of conflicts of interest. We are a public charity, which reduces and simplifies our taxation. We use modern, low-overhead money transfer methods such as transferwise.com and constantly scan for better ones. Anyone who considers donating should know that about every five dollars donated goes straight to pay for one hour of an exceptional graduate student’s time.

Mike: Are there more applications in the queue? Do you plan to extend scholarships to other universities?

Andrei: UPB seems to be off to a great start, but it’s also a happy case for many reasons: it’s my undergrad alma mater, we know professors there, and we don’t need to pay tuition. If we wanted to extend a scholarship to another university we’d need to avail ourselves of similar strategic advantages. Needless to say, if anyone who reads this has ideas on the matter, please contact me.

Anyhow, for the time being, we got one more strong DLang UPB scholarship application literally today.

Mike: To close out, is there anything you’d like to say to people who’d like to help out?

Andrei: I’m very excited about this scholarship program and possible extensions to it. The reason for my excitement is that this is but a part of a larger strategy. Allow me to explain.

Up until now, we had no idea what to do with money even if we had it. A while ago, I met this potential donor who said, “OK, say I gave the Foundation half a million dollars over two years, no strings attached. What would you do with it?” To my own surprise, I had only vague answers. I asked Walter the same question, and he had even less of a clue than me.

So then I figured it’s essential for the Foundation to have a strong response to that. I’m a big believer in the adage “luck helps the prepared”, of which the converse is “luck is wasted on the unprepared”. By that paradigm, not knowing what we’d do with money was a definite way to ensure we’d never be big. Now that we have the scholarship program, there exists a powerful reason for people to donate to the Foundation: donations help us find and support good students to work on high-impact D-related projects that push the state of CS systems research forward.

Another thing that would be great to have “donations” of is contributor time. Receiving more students starts pushing against our management capacity. Currently, and somewhat to my surprise, I am effectively a manager, seeing that all of these things I just gave you an earful of (bringing money in to the Foundation, managing bootcamp, finances, operations) take enough time to be a full-time job that leaves little time for coding. At some point, I won’t be able to help everyone with their research, so I’ll need to delegate some of that work to other folks. I’m talking any capacity here – from code reviews to managing to co-authoring papers to co-advising.

There are more things I have in mind, but it’s early to share those. In brief, we need to organize ourselves for further growth. What’s clear to me is we’re no longer a seat-of-the-pants operation in a (virtual) basement. The D Language is exiting its adolescence.