Sign in to follow this  

Electronic Arts Standard Template Library

This topic is 3856 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

This paper came up on programming.reddit today: Electronic Arts Standard Template Library. Abstract:
Gaming platforms and game designs place requirements on game software which differ from requirements of other platforms. Most significantly, game software requires large amounts of memory but has a limited amount to work with. Gaming software is also faced with other limitations such as weaker processor caches, weaker CPUs, and non-default memory alignment requirements. A result of this is that game software needs to be careful with its use of memory and the CPU. The C++ standard library's containers, iterators, and algorithms are potentially useful for a variety of game programming needs. However, weaknesses and omissions of the standard library prevent it from being ideal for high performance game software. Foremost among these weaknesses is the allocator model. An extended and partially redesigned replacement (EASTL) for the C++ standard library was implemented at Electronic Arts in order to resolve these weaknesses in a portable and consistent way. This paper describes game software development issues, perceived weaknesses of the current C++ standard, and the design of EASTL as a partial solution for these weaknesses.
It's a very interesting read.

Share this post


Link to post
Share on other sites
I caught that too.

I think some of the observations within were based on a particular implementation of the STL, though e.g. the stuff about void-pointers in node-based containers.

But it is an interesting discussion, certainly.

Edd

Share this post


Link to post
Share on other sites
Quote:
Original post by the_edd
I think some of the observations within were based on a particular implementation of the STL, though e.g. the stuff about void-pointers in node-based containers.

Well, that's the point--they wanted unified behavior across different implementations.

Share this post


Link to post
Share on other sites
Well, they can't demand something like that, IMO, at least not in this way.

Sticking to the standard does give unified behaviour. That's the whole point of the standard. They're talking about implementation details, which the standard does not define and nor should it; it's up to the library implementer to decide what's the best way to do something for a particular system.

If the implementer of the library they're using isn't doing a very good job, they should take it up with them and not impose rules on every implementer. I realise that's not what they're doing.

A lot of their suggestions and comments are rational and well-justified and I agree with a lot of what is said.

But I think in a few of the situations highlighted, the issue seems to be with a particular implementation of the standard library that they're using.

Edd

Share this post


Link to post
Share on other sites
I understand what you mean--you can't specify, in the standard, that implementations should provide the programmer a proper view of the data with a debugger. That's outside the scope of a language standard. That's why they came up with their own (cross-platform) implementation that guarantees it.

Share this post


Link to post
Share on other sites
Very interesting read, thanks for posting it.

The document sums up perfectly why we have banned the use of the STL/standard library in all of our corporate projects, and replaced it by our own implementation. On the other hand, it gives some very interesting ideas about optimizing and extending this in-house implementation.

Quote:

Sticking to the standard does give unified behaviour. That's the whole point of the standard.

While this is true, it is also its greatest weakness. As a programmer, I expect a certain amount of functionality and ease of use from a library. This is specifically true for areas such as efficient debugging, efficient and flexible performance and storage characteristics, low memory footprint, highly controllable multithreaded behaviour, cross-DLL boundary safety, etc.

These are all implementation details, and thus ignored by the current standard. Yet, they are immensely important.

Share this post


Link to post
Share on other sites
Quote:
While this is true, it is also its greatest weakness. As a programmer, I expect a certain amount of functionality and ease of use from a library. This is specifically true for areas such as efficient debugging, efficient and flexible performance and storage characteristics, low memory footprint, highly controllable multi-threaded behaviour, cross-DLL boundary safety, etc.
These are all implementation details, and thus ignored by the current standard. Yet, they are immensely important.


Well the standard doesn't mention DLLs or multithreading (yet) at all. It can't mention DLLs because they're tied to a particular platform. One could argue that something related to shared libraries could be added but the differences in the way shared libraries are handled between platforms is so broad that it would be pointless trying to extract vague and tenuous commonality for potential standardisation.

Doing any kind of multi-threading in C++ is dangerous unless you know your compiler and platform inside out (which you may, of course) because the standard behaviour is defined in terms of a single threaded virtual machine (for now) and the guarantees for different platform/compiler combinations vary greatly in the wild.

I guess I'm just saying it's unfair to criticise a platform-neutral standard for failing to standardise something platform specific. I'm not entirely sure that's what you were doing, though :)

If there are other issues with the library, it's often the implementation that needs to be improved and not the specification. For instance, a large number of the suggestions made in the article are only improvements over a particular implementation.

I certainly agree that debug-ability is generally quite bad, though it doesn't need to be. The library being developed for the Open Watcom compiler is very readable, for example.

One of the things that I really agree with is that the whole allocator concept, as it stands currently, is just severely flawed for a number of reasons. I really hope that gets sorted in the standard some time soon.

Edd

Share this post


Link to post
Share on other sites
It doesn't really matter what they do.

Standard STL is important for portability and re-use. In a large corporation working with proprietary confidential code, external code re-use isn't a big deal, and their code will not be published as general purpose.

So the only benefit of remaining standard compliant is void.

That said, STL is generic. Game development on the other hand has always looked for highly tuned solutions. The mere adoption of STL seems like big step to me.

But EA is interested into one thing only - getting things done. If it means breaking the standard, or abandoning it completely, they will. It's purely practical - if it gets their job done faster/better/more reliably/more conveniently, why not.

This is interesting read, and it is clearly stated as EA STL. It's something they use for themselves, but during cursory read, I didn't see any implication that they want to replace STL standard.

Share this post


Link to post
Share on other sites
It works for them, obviously. But they're also a large enough company to have staff that can be dedicated to development and maintainance. Most of us, unfortunately, don't have that luxury -- most non-publisher entities don't either.

Good for them though, interesting read.

Share this post


Link to post
Share on other sites
Quote:
Original post by the_edd
I guess I'm just saying it's unfair to criticise a platform-neutral standard for failing to standardise something platform specific. I'm not entirely sure that's what you were doing, though :)

I wouldn't call many of the listed points platform specific. And even if some of them were, I question the viability of a completely platform neutral standard library altogether, at least for C++. For EA, for myself and for many others, it's exactly this lack of platform specific adaptation that makes the STL unusable in practice.

What good are container classes when I can't pass them over a DLL boundary, especially in a modern plugin driven application that resides to 99% in DLLs ? How could I use a standard algorithm that isn't thread safe in a heavily multithreaded application, especially in the times of multicore CPUs ? How could I rely on non-specified, opaque, and often highly inefficient storage allocation schemes for objects that are created and destroyed many times a second, in performance critical code ?

On top of that, the STL has a lot of inherent design flaws. Yes, Boost corrects many of them, but it doesn't address the implementation issues mentioned above. Not mentioning the additional bloat coming with it.

If you look at STL related criticism from actual industry programmers (ie. not the academics sitting around and deriving standards, but the ones actually using them in real world projects), you tend to always stumble across the same issues over and over again. These issues can, and should be addressed in a standard.

Shared library and thread safety can be mandated without leaving platform neutrality. Memory allocation behaviour can be standarized, or better hooks for custom allocators can be provided. Debug support is harder, I agree. But at least non-cryptic symbols can be mandated, as well as banning void pointers in places where they don't belong.

And finally, standard library subsystems should be "reality checked" much harder before promoting them into the standard. iostreams anyone ?

Share this post


Link to post
Share on other sites
It looks like about equal parts of actual, useful, obvious-in-retrospect fixes to the Standard--it's difficult to argue with a better allocator interface and passing predicates by reference--and special purpose fixes for console platforms. Most of the former category really deserves to be rolled into the next TR. That includes stuff like intrusive_list which I suspect will get a much chillier reception than if Boost had been offering it up.

Share this post


Link to post
Share on other sites
I fully agree with Yann L. ... why do they still use STL? Next-gen consoles are so sensitive to some C++ constructs. Using STL is the perfect way to a trainwreck.
I guess some guys at EA have to much time here. Most companies I know did the same as Yann described it.

- Wolf

Share this post


Link to post
Share on other sites
Quote:
Original post by Yann L
Quote:
Original post by the_edd
I guess I'm just saying it's unfair to criticise a platform-neutral standard for failing to standardise something platform specific. I'm not entirely sure that's what you were doing, though :)

I wouldn't call many of the listed points platform specific.


Sorry, here I was talking about the threading/DLL stuff in the post to which I replied, not the stuff brought up in the EA document as a whole, necessarily.

Quote:
And even if some of them were, I question the viability of a completely platform neutral standard library altogether, at least for C++. For EA, for myself and for many others, it's exactly this lack of platform specific adaptation that makes the STL unusable in practice.

What good are container classes when I can't pass them over a DLL boundary, especially in a modern plugin driven application that resides to 99% in DLLs ?


I can't argue with this point. But it's unfair to criticise the STL for something it was not designed to do, nor can it be designed to do. Passing template classes over DLL boundaries is fraught with danger, whether the templates are from the STL or elsewhere. It's fine if the implementation of the templates classes are "ABI stable" (in the appropriate sense for the platform), but if they're not you can't have pluggable/upgradable libraries.

I'm interested to hear that you "question the viability of a completely platform neutral standard library altogether". What alternative approach is there for a language whose overriding goal is to be platform neutral? (serious question!)

Quote:
How could I use a standard algorithm that isn't thread safe in a heavily multithreaded application, especially in the times of multicore CPUs ?


How can you use *any* algorithm or function in such a situation? The C++ standard simply has nothing to say on multi-threading yet. This issue isn't restricted to the STL. The whole standard lacks any notion of threads (until ~2009 IIRC). If you're using multi-threading now, you're on your own (or part of a wider community of people who are also on their own :)). You have to check what guarantees your specific compiler/processor(s)/caches/OS give you in *any* C++ code you write, whether it uses the standard library or not.

Quote:
How could I rely on non-specified, opaque, and often highly inefficient storage allocation schemes for objects that are created and destroyed many times a second, in performance critical code ?


This is indeed one of the areas where I really agree with EA's proposal reflects what the "community" knows already; that the allocator specification is seriously flawed.

Quote:
If you look at STL related criticism from actual industry programmers (ie. not the academics sitting around and deriving standards, but the ones actually using them in real world projects), you tend to always stumble across the same issues over and over again. These issues can, and should be addressed in a standard.


The load has to be shared between the standardisation committee, compiler implementers and library implementers. A lot of the stuff the document mentions are issues found in a specific implementation.

A large number of the people on the committee are involved in real world development. But games programming is a particularly constrained/demanding programming niche and it's voice perhaps isn't heard as loudly as it could be.

Quote:
Shared library and thread safety can be mandated without leaving platform neutrality.


I'm not sure any kind of standardisation in this area would be particularly beneficial. I say this because the common ground between shared library implementations across all the platforms that currently have C++ implementations (in real-world use) is so narrow that any attempt to standardise on this would yield wording lacking in specifics and we'd be in no better shape than we're in now, in this regard.

Quote:
Memory allocation behaviour can be standarized, or better hooks for custom allocators can be provided.


Yes, I think fixing the allocator mechanism is the way forward. Memory allocation behaviour is too heavily tied to the OS (if there is one) in a number of cases to mandate specific behaviour in the general case.

Quote:
Debug support is harder, I agree. But at least non-cryptic symbols can be mandated, as well as banning void pointers in places where they don't belong.


The void pointer thing is an implementation issue. If a particular vendor's library is made using void pointers in the node-like structures, then (IMVHO) it's a bad implementation and the vendor should be asked to fix it.

However, there may be very good reasons why the implementation has used void pointers (not that I can think of any, personally) and if there is reason to use void pointers in some cases, the standard should not mandate that void pointers are not to be used. That would be detrimental to a the library implementation on a given platform. Then you'd hear the argument from the opposite side of the fence to loosen up the restriction again. It *has* to be a QOI issue wrt to the library implementation. Bug reports should be filed against the library.

Quote:
And finally, standard library subsystems should be "reality checked" much harder before promoting them into the standard. iostreams anyone ?


That's one of the reasons that boost exists, of course. I think the committee regards real-world experience as a very valuable asset after the whole "export" experience.

<semi-ot>
Incidentally, I'm interested in the problems with iostreams in respect to games programming. We use our own I/O subsystem at work, but it seems worse than using iostreams. No one there has ever been able to explain to me why we didn't just use iostreams in the first place.

Are there any URLs you could give me? Maybe a PM would be most appropriate?
</semi-ot>

Edd

Share this post


Link to post
Share on other sites
Quote:
It looks like about equal parts of actual, useful, obvious-in-retrospect fixes to the Standard--it's difficult to argue with a better allocator interface and passing predicates by reference--and special purpose fixes for console platforms. Most of the former category really deserves to be rolled into the next TR. That includes stuff like intrusive_list which I suspect will get a much chillier reception than if Boost had been offering it up.


It might not get as chilly a recpetion as you'd expect especially since intrusive containers where recently accepted into boost, although they werent in time for the 1.34.0 release.

Share this post


Link to post
Share on other sites
Quote:
Original post by the_edd
Quote:
How could I use a standard algorithm that isn't thread safe in a heavily multithreaded application, especially in the times of multicore CPUs ?


How can you use *any* algorithm or function in such a situation? The C++ standard simply has nothing to say on multi-threading yet.


No reason it couldn't, though. The only issue I think is that the non-deterministic nature of thread safety is that it incurs overhead in situations where you can guarantee not needing that overhead. I suppose this is where another trait or policy parameter could come in.

Quote:
The void pointer thing is an implementation issue. If a particular vendor's library is made using void pointers in the node-like structures, then (IMVHO) it's a bad implementation and the vendor should be asked to fix it.

However, there may be very good reasons why the implementation has used void pointers (not that I can think of any, personally) and if there is reason to use void pointers in some cases, the standard should not mandate that void pointers are not to be used.


When compiling templates, it's common to pass data around as void pointers between functions that don't care about the actual type. You could have a whole chain of generic functionality that manipulates void pointers as long as the endpoints are typesafe. This speeds up compilation and reduces code bloat (which just gets trimmed away at link time, presumably).

Quote:
<semi-ot>
Incidentally, I'm interested in the problems with iostreams in respect to games programming. We use our own I/O subsystem at work, but it seems worse than using iostreams. No one there has ever been able to explain to me why we didn't just use iostreams in the first place.


Personally I quite like iostreams, though there's little doubt that they can feel a bit unwieldy. They also seem to be slower than stdio in practice, though in theory they could be faster. I find the differences largely unimportant though, because for 90% of critical applications I'm not doing formatted output, and so the interface for iostreams is not particularly different from stdio.

Share this post


Link to post
Share on other sites
Quote:
Original post by the_edd
[...]<semi-ot>
Incidentally, I'm interested in the problems with iostreams in respect to games programming. We use our own I/O subsystem at work, but it seems worse than using iostreams. No one there has ever been able to explain to me why we didn't just use iostreams in the first place.

Are there any URLs you could give me? Maybe a PM would be most appropriate?
</semi-ot>

Edd
I recently had to make a custom file input class at work because the ifstream class (or one of it's ancestors etc) uses a signed 32-bit value to represent file position somewhere along it's call chain even though the actual input type to the set-position function could hold 232-1 (so much for compile-time asserts doing any good). Of course, this problem only shows up for very large files (over 2 GiB) and is entirely implementation dependant, but it was quite annoying. For the record, the problem occured with MSVC 7.1 and the library that comes with it.

Share this post


Link to post
Share on other sites
Quote:
...But they're also a large enough company to have staff that can be dedicated to development and maintainance. Most of us, unfortunately, don't have that luxury -- most non-publisher entities don't either.

EASTL was largely written and is maintained by a single person, in his spare time.

Share this post


Link to post
Share on other sites
me wants very badly, whilst i love stl + use it heaps i have a few issues with it ( + have to replace some of it with my own similar stuff ), but these seem to be solved with EASTL
any chance this is gonna end up in the public domain

Share this post


Link to post
Share on other sites
Quote:
Original post by Kylotan
No reason it couldn't, though. The only issue I think is that the non-deterministic nature of thread safety is that it incurs overhead in situations where you can guarantee not needing that overhead. I suppose this is where another trait or policy parameter could come in.


I agree. I use a Policy based Multithreading system in my code. You can very easily include any threading library or a single threaded version that will just optimize away the empty calls (assuming a good compiler).

Share this post


Link to post
Share on other sites

This topic is 3856 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this