Electronic Arts Standard Template Library for C++ Open Sourced | Hacker News Reader

Electronic Arts Standard Template Library for C++ Open Sourced

github.com

207 pointshising57 comments

We on the Rust team got to speak about the lessons learned from the EASTL with Paul Pedriana (the author of much of it) while designing the Rust standard library. It's a significant influence on the proposed allocators API currently in RFC. The EASTL is worth looking at for anyone interested in designing libraries that work well in low-memory environments. (Much of this library was written with devices like the Nintendo DS in mind, which had 4 MB--4 MB!--of RAM as I recall.)

I had the pleasure of being Paul's intern way back in 2000. At the time, Paul was at Maxis and if IIRC the library actually had its roots in the C++ frameworks Paul built for SimCity 3000. Those games actually were quite a bit ahead, engineering-wise, in terms of the C++ of the day.

STL is maybe a bit missleading because it doesn't seem like it is a drop-in replacement for the STL.

However, this is certainly interesting because the emphasis on speed (and thus also on simplicity) is what I'm sometimes missing in the real STL or in Boost. That's exactly what you need in a game but also in much other performance critical code.

As far as I remember, Chrome has used the STL earlier. But I looked now and I see this: https://chromium.googlesource.com/chromium/blink/+/master/So...

Gecko also seem to have a lot of custom stuff: https://github.com/mozilla/gecko-dev/tree/master/xpcom/strin...

Doom3 idLib: https://github.com/id-Software/DOOM-3-BFG/tree/master/neo/id...

Unreal engine: https://answers.unrealengine.com/questions/2695/rocket-and-t...

You'll find much more similar libs when you search in some of the big games.

What parts of the EASTL are faster than the normal STL? Does it have better maps?

Edit: From a look at the source it definitely at least has some extra map classes for more specialized uses.

When I first saw that commit, I was all wtf?? wtf?! Thanks for that explanation.

I measured the sort to be slightly faster: https://www.reddit.com/r/programming/comments/451yje/ea_open...

For the lazy:

std_sort_time: 0.08805380923877237s (11.908354778344838 M keys/s)

eastl_sort_time: 0.07010223707038676s (14.957810817751337 M keys/s)

EA's sort seems to respond better to full program optimisation than std::sort. Platform: vs2012 x64, i7 CPU.

One goal of EASTL is to be faster in non-optimized builds compared to other variants. If a game is running too slow to be playable, it can become impossible to debug! This was especially a problem on consoles with no OOE. It achieves this by sacrificing a lot of encapsulation and accepting non-DRY, manually inlined function implementations.

I didn't realise this was a goal, but it's good that it was. C++'s prime faults tend to be spiteful iteration time (common cause: too many templates) and appalling performance in unoptimized builds (common cause: too many function calls, possibly due to overloaded operators and overly-finely-grained code that relies on inlining not to run like shit).

The famous maxim about how much cleverer you have to be to debug code than to write it always applies! No need to make things worse by forcing yourself to debug the optimized build.

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n227... search for "20 - Performance comparison"

> As far as I remember, Chrome has used the STL earlier. But I looked now and I see this:

The WTF (Web Template Framework) is actually inherited from WebKit and used in the core rendering engine. I'm not sure how widely it's used in the Google parts of Chromium.

> Gecko also seem to have a lot of custom stuff

That's the old XPCOM stuff. While those string types continue to get a lot of use, the closest analogue to the STL is MFBT: https://github.com/mozilla/gecko-dev/tree/master/mfbt

You should see what was in the LibreOffice codebase at one point!

That simply predated the STL by a number of years, no?

Many, many years :-) it wasn't a true criticism

Chromium uses STL, WebKit (forked to Blink) uses custom stuff.

I've never had a problem shipping 60hz games with STL even on consoles.

Writeup on the key design and advantages of EASTL for their target platforms (game consoles): http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n227...

I have worked for game companies making large console games both with the STL and without. One thing I noticed about STL is that it really bloats the build times because the STL headers are so massive. I did some analysis of the preprocessor output one time and found that just including a couple of headers like vector.h and string.h would increase the size of the preprocessor output by 80000 to 100000 lines, even for a cop file that is otherwise trivially small. Typically almost every cpp file in the codebase would either directly use STL headers or bring them in as dependencies, and so in a codebase of a few thousand files you are talking about hundreds of millions of extra lines of code that the compiler has to churn through. This amounted to each cpp file talking several seconds to compile and the entire codebase taking most of an hour to rebuild. People would not have been able to survive that without using Incredibuild to farm off compilation to other machines. The company I currently work at does not use STL and so largely avoids this problem. I an curious to what extent EASTL has this problem or avoids it.

EASTL still has this problem. It's worse on Windows where the prerequisite system header (ie: yvals.h, etc.) can bring in a ton of bloat. Until modules are a reliable thing and we can take advantage of them in a reasonable cross platform way it will still remain a problem.

Isn't part of this addressed by taking advantage of the new C++ 11 extern template feature? http://www.stroustrup.com/C++11FAQ.html#extern-templates

The real solution is 'import' but we probably won't see that in ++17

This was open sourced years ago on the EA open source page: http://j.mp/1Kh4L2C

It's just on Github now.

Nope; they open sourced a tiny part of it before. Now they've open sourced the entire thing

The previously released version was significantly incomplete (it only included what was needed for the copy of webkit they embedded in some games), was years out of date, and was GPL rather than BSD.

In addition to what others have said, this newest release is 3-clause BSD, whereas previous releases were LGPL.

A quick reference guide in PDF is available at https://github.com/electronicarts/EASTL/blob/master/doc/EAST.... Lists all Algorithms, functions etc.

Cute. It's fun to see game programmer code. This is really C with a little C++. Lots of pointer casts, comments like "The user must provide ample buffer space, preferably 256 chars or more." There's a lot of stuff in there to deal with Microsoft Visual C++'s interpretation of the language, which prior to 2010, was kind of off.

Why does "swap" use EASTL/move_help.h? There are things that can go wrong with a move that can't go wrong with a swap. Move is a swap with a constraint that the destination be empty.

(Doing things through swapping has its uses. It preserves single ownership, for example.)

> Cute. It's fun to see game programmer code.

This. I work almost exclusively with game programmers and it can be ... difficult at times. They seem to be largely unaware of the larger computer science community that's existed since the mid sixties, often "discovering" things that were solved by the science years ago.

On the other hand, game programmers are just as frequently the only ones exercising anything close to the full functionality of today's hardware. It's kind of depressing how little use SIMD, multicore, and GPU (compute or otherwise) get outside of games. Games have done a pretty good job keeping up with the ending of Moore's Law for sequential code, but we continue to use our old sequential libraries and leave so much performance on the table in the app world.

I do agree that the apps and server world is ahead, in many cases way ahead, in terms of effective development practices and programming languages. But we've lost sight of how to get performance out of the hardware.

> game programmers are just as frequently the only ones exercising anything close to the full functionality of today's hardware

I know some ML and HPC cats who obsess about hitting peak gigaflops...

Yeah, I was too broad there, sorry about that. There are definitely a few fields like scientific computing and HFT that are very good at extracting performance out of modern hardware.

Still, app and server developers, by and large, have not been able to do this (and I count myself among them!) We use languages with no support for SIMD, we stick to language implementations without optimizing compilers, single-threaded language implementations are very popular, we ignore GPU computing despite the fact that the die space reserved for the GPU is as large or larger than the die space reserved for the CPU cores nowadays, and so on.

I was re-exploring that issue recently. It wasn't obvious to me which of two strategies I commonly saw are best: extend existing languages with parallel constructs as in Cilk/C, ParaSail/Ada, or Lime/Java; create custom languages + compilers like Cray's Chapel or academic Triolet whose output cleanly integrates with apps in an existing language. My uncertainty comes from the fact that general-purpose languages founded in sequential use might be too hard to max out on arbitrary multi-core & CPU architectures. What's your opinion on which looks to be the best route so far?

Cilk http://supertech.lcs.mit.edu/cilk/

ParaSail http://www.embedded.com/design/other/4375616/ParaSail--Less-...

Lime Compilation http://researcher.watson.ibm.com/researcher/files/us-bacon/D...

Chapel http://chapel.cray.com/overview.html

Triolet http://impact.crhc.illinois.edu/shared/Papers/dissertation-r...

Anything and everything. I don't believe there's a one-size-fits-all solution for parallelism.

This is a really good counterpoint, and I think it reflects how the client's nature can very much shape the development process.

Big-budget video games often have very different feature requirements compared to ofter types of software, not to mention especially strict deadlines, so their attitudes towards shipping products is going to be different.

The problem is that the majority of applications we get hired to develop are either some kind of CRUD or data transformation project.

The constraints and things that matter are different. I've had both experiences like you and also the opposite ones. As an example the constant factor in time usage is surprisingly important in games. Amortized time consumption is not the absolute end all be all.

Designing any soft realtime application is subtly different from traditional application. Your frametime budget is 16ms. It's rock solid. You spend 17ms and you're down to 30fps and you could've just spent 33ms.

That's actually the reason why garbage collection is big no no in games. One cannot afford even 1ms gc pauses. And in server world that's considered blazingly fast. If a game is for some reason developed using a language with GC it's just skipped by making object pools. And then tediously checking that no allocations and freeing actually happens during a frame.

> Move is a swap with a constraint that the destination be empty.

Is there actually any constraint here? I thought the only constraint on a moved-from object is that you can't use it in the current state.

The standard defines moved from objects (standard library types, at least) to be in a 'valid but unspecified state'. For container types like std::vector, 'valid but unspecified' usually means empty.

`swap` uses `move` to enable swapping objects that can only be moved but not copied (e.g., std::unique_ptr<T>). Note that this swap implementation is meant to be generic---types may implement their own specific `swap` that performs no copies or moves whatsoever. Example:

  namespace NS {
    struct S {
      friend void swap(S& a, S& b) {
        // do something interesting here
      }
    };
  }

  // later..
  template<typename T>
  void f(T& a, T& b) {
    using std::swap;
    swap(a, b); // calls NS::swap(a, b) if T = NS::S
  }

Looks like way more than a little C++ to me. I mean, it's a template library!

C with a little C++? It's a full C++11 implementation of each of the components it implements, modulo the namespace and allocator change. Perhaps it seems simpler to you because you are used to complicated implementations.

Scott Wardle gave an interesting talk at CppCon 2015 which mentions EASTL a bit, with the reasons they use it (and other non-standard tools): “Memory and C++ debugging at Electronic Arts” https://youtu.be/8KIvWJUYbDA

CppCon 2015 was also the site of the first formal meeting of SG14, the game developer study group of the C++ standards committee. Michael Wong has just announced that it will meet again at CppCon 2016: https://groups.google.com/a/isocpp.org/forum/?fromgroups#!to...

Note that EA had already released some of the code in 2010: https://github.com/paulhodge/EASTL

But 2016 version is full HD. Can't wait for 2017.

And I thought my workplace was the last shop in the world to still write new code in hungarian notation ...

LibreOffice still does.

A lot of C++ code I see is in Hungarian notation. Less true for pure C.

Even Microsoft is now recommending against it in their style guides.

That's "bad" systems hungarian instead of "good" apps hungarian

http://www.joelonsoftware.com/articles/Wrong.html

If you use C++, you should really be using a separate type for this, rather then rely on variable names. The compiler is much better at catching these things than you are.

Hungarian is still somewhat common in game development. Getting less common though.

The "Hungarian" in EASTL is very light. It's not even really Hungarian; it's mostly just m prefixes for members, p for pointers, and n for numbers. Hungarian is a far more draconian set of conventions.

Looks like build is failing !

I just upvoted the same news just 4 days ago: https://news.ycombinator.com/item?id=11069305

There is some issue with duplicates in HN, I think points should go to the original poster, more if it's recent.

Eh, is it really that big a deal? I have a few times posted something which gets no attention and is then reposted with up votes and comments (sometimes only a few hours later). Maybe a little irksome, but I don't think HN karma/score/points should be that big of a concern.

Now we can at least explain with code examples why Electronic Arts Games suck so much.

That's a pretty low punch under the belt. If you are being serious, please give some examples of why this STL sucks. Corporations like EA, which is a long hauled bureaucratic labyrinth should be celebrated for open sourcing code.

Reply on news.ycombinator.com