diff options
Diffstat (limited to 'doc/html/EASTL Maintenance.html')
| -rw-r--r-- | doc/html/EASTL Maintenance.html | 292 |
1 files changed, 292 insertions, 0 deletions
diff --git a/doc/html/EASTL Maintenance.html b/doc/html/EASTL Maintenance.html new file mode 100644 index 0000000..aaca955 --- /dev/null +++ b/doc/html/EASTL Maintenance.html @@ -0,0 +1,292 @@ +<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"> +<html> +<head> + <title>EASTL Maintenance</title> + <meta content="text/html; charset=us-ascii" http-equiv="content-type"> + <meta name="author" content="Paul Pedriana"> + <meta name="description" content="Information for the EASTL maintainer."> + <link type="text/css" rel="stylesheet" href="EASTLDoc.css"> +</head> +<body> + +<h1>EASTL Maintenance</h1> +<h2><span style="font-style: italic;"><a name="Introduction" id="Introduction"></a></span>Introduction</h2> +<p>The purpose of this document is to provide some necessary background for anybody who might do work on EASTL. Writing + generic templated systems like EASTL can be surprisingly tricky. There are numerous details of the C++ language that + you need to understand which don't usually come into play during the day-to-day C++ coding that many people do. It is + easy to make a change to some function that seems proper and works for your test case but either violates the design + expectations or simply breaks under other circumstances.<br> + <br> + It may be useful to start with an example. Here we provide an implementation of the count algorithm which is seems +simple enough. Except it is wrong and while it will compile in some cases it won't compile in others:</p> +<pre class="code-example">template <class InputIterator, class T> +int count(InputIterator first, InputIterator last, const T& value) +{ + int result = 0; + + for(; first < last; ++first){ + if(*first == value) + ++result; + } + + return result; + } </pre> +<p>The problem is with the comparison 'first < last'. The count algorithm takes an InputIterator and operator< is +not guaranteed to exist for any given InputIterator (and indeed while operator< exists for vector::iterator, it +doesn't exist for list::iterator). The comparison in the above algorithm must instead be implemented as 'first != +last'. If we were working with a RandomAccessIterator then 'first < last' would be valid.</p> +<p>In the following sections we cover various topics of interest regarding the development and maintentance of EASTL. + Unfortunately, this document can't cover every aspect of EASTL maintenance issues, but at least it should give you a +sense of the kinds of issues.</p> + +<h2> <a name="Language_Standard" id="Language_Standard"></a>C++ Language Standard</h2> +<p>First and foremost, you need to be familiar with the C++ standard. In particular, the sections of the standard related + to containers, algorithms, and iterators are of prime significance. We'll talk about some of this in more detail below. + Similarly, a strong understanding of the basic data types is required. What is the difference between ptrdiff_t and +intptr_t; unsigned int and size_t; char and signed char?</p> +<p>In addition to the C++ language standard, you'll want to be familiar with the C++ Defect Report. This is a continuously + updated document which lists flaws in the original C++ language specification and the current thinking as the +resolutions of those flaws. You will notice various references to the Defect Report in EASTL source code.</p> +<p>Additionally, you will want to be familiar with the C++ Technical Report 1 (as of this writing there is only one). This + document is the evolving addendum to the C++ standard based on both the Defect Report and based on desired additions to +the C++ language and standard library.</p> +<p>Additionally, you will probably want to have some familiarity with Boost. It also helps to keep an eye on + comp.std.c++ Usenet discussions. However, watch out for what people say on Usenet. They tend to defend GCC, Unix, std + STL, and C++ to a sometimes unreasonable degree. Many discussions ignore performance implications and +concentrate only on correctness and sometimes academic correctness above usability.</p> +<h2> <a name="Langauge_Use" id="Langauge_Use"></a>Language Use</h2> +<p>Macros are (almost) not allowed in EASTL. A prime directive of EASTL is to be easier to read by users and most of + the time macros are an impedence to this. So we avoid macros at all costs, even if it ends up making our development + and maintenance more difficult. That being said, you will notice that the EASTL config.h file uses macros to control + various options. This is an exception to the rule; when we talk about not using macros, we mean with the EASTL +implementation itself.</p> +<p>EASTL assumes a compliant and intelligent C++ compiler, and thus all language facilities are usable. However, we +nevertheless choose to stay away from some language functionality. The primary language features we avoid are:</p> +<ul> + <li>RTTI (run-time-type-identification) (this is deemed too costly)</li> +<li>Template export (few compilers support this)</li> +<li>Exception specifications (most compilers ignore them)</li> +</ul> +<p>Use of per-platform or per-compiler code should be avoided when possible but where there is a significant advantage to + be gained it can and indeed should be used. An example of this is the GCC __builtin_expect feature, which allows the + user to give the compiler a hint about whether an expression is true or false. This allows for the generation of code +that executes faster due to more intelligent branch prediction.</p> +<h2> <a name="Prime_Directives" id="Prime_Directives"></a>Prime Directives</h2> +<p>The +implementation of EASTL is guided foremost by the following directives which are listed in order of importance.</p> +<ol> +<li>Efficiency (speed and memory usage)</li> +<li>Correctness (doesn't have bugs)</li> +<li>Portability (works on all required platforms with minimal specialized code)</li> +<li>Readability (code is legible and comments are present and useful)</li> +</ol> +<p>Note that unlike commercial STL implementations which must put correctness above all, we put a higher value on + efficiency. As a result, some functionality may have some usage limitation that is not present in other similar systems +but which allows for more efficient operation, especially on the platforms of significance to us.</p> +<p>Portability is significant, but not critical. Yes, EASTL must compile and run on all platforms that we will ship games + for. But we don't take that to mean under all compilers that could be conceivably used for such platforms. For example, + Microsoft VC6 can be used to compile Windows programs, but VC6's C++ support is too weak for EASTL and so you simply +cannot use EASTL under VC6.</p> +<p>Readability is something that EASTL achieves better than many other templated libraries, particularly Microsoft STL and + STLPort. We make every attempt to make EASTL code clean and sensible. Sometimes our need to provide optimizations + (particularly related to type_traits and iterator types) results in less simple code, but efficiency happens to be our +prime directive and so it overrides all other considerations.</p> + +<h2> <a name="Coding_Conventions" id="Coding_Conventions"></a>Coding Conventions</h2> +<p>Here we provide a list of coding conventions to follow when maintaining or adding to EASTL, starting with the three +language use items from above:</p> +<ul> +<li>No RTTI use.</li> +<li>No use of exception specifications (e.g. appending the 'throw' declarator to a function).</li> +<li>No use of exception handling itself except where explicitly required by the implementation (e.g. vector::at).</li> +<li>Exception use needs to savvy to EASTL_EXCEPTIONS_ENABLED.</li> +<li>No use of macros (outside of config.h). Macros make things more difficult for the user.</li> +<li>No use of static or global variables.</li> +<li>No use of global new, delete, malloc, or free. All memory must be user-specifyable via an Allocator parameter +(default-specified or explicitly specified).</li> +<li>Containers use protected member data and functions as opposed to private. This is because doing so allows +subclasses to extend the container without the creation of intermediary functions. Recall from our <a href="#Prime_Directives">prime directives</a> above that performance and simplicity overrule all.</li> +<li>No use of multithreading primitives. </li> +<li>No use of the export keyword.</li> +<li>We don't have a rule about C-style casts vs. C++ static_cast<>, etc. We would always use static_cast except +that debuggers can't evaluate them and so in practice they can get in the way of debugging and tracing. However, if the +cast is one that users don't tend to need to view in a debugger, C++ casts are preferred.</li> +<li>No external library dependencies whatsoever, including standard STL. EASTL is dependent on only EABase and the +C++ compiler. </li> +<li>All code must be const-correct. This isn't just for readability -- compilation can fail unless const-ness is used +correctly everywhere. </li> +<li>Algorithms do not refer to containers; they refer only to iterators.</li> +<li>Algorithms in general do not allocate memory. If such a situation arises, there should be a version of the +algorithm which allows the user to provide the allocator.</li> +<li>No inferior implementations. No facility should be added to EASTL unless it is of professional +quality.</li> +<li>The maintainer should emulate the EASTL style of code layout, regardless of the maintainer's personal preferences. +When in Rome, do as the Romans do. EASTL uses 4 spaces for indents, which is how the large majority of code within EA +is written.</li> +<li>No major changes should be done without consulting a peer group.</li> +</ul> + +<h2><a name="Compiler_Issues" id="Compiler_Issues"></a>Compiler Issues</h2> +<p>Historically, templates are the feature of C++ that has given C++ compilers the most fits. We are still working with + compilers that don't completely and properly support templates. Luckily, most compilers are now good enough to handle +what EASTL requires. Nevertheless, there are precautions we must take.</p> +<p>It turns out that the biggest problem in writing portable EASTL code is that VC++ allows you to make illegal statements + which are not allowed by other compilers. For example, VC++ will allow you to neglect using the typename keyword in +template references, whereas GCC (especially 3.4+) requires it.</p> +<p>In order to feel comfortable that your EASTL code is C++ correct and is portable, you must do at least these two +things:</p> +<ul> +<li>Test under at least VS2005, GCC 3.4+, GCC 4.4+, EDG, and clang. </li> +<li>Test all functions that you write, as compilers will often skip the compilation of a template function if it isn't +used.</li> +</ul> +<p>The two biggest issues to watch out for are 'typename' and a concept called "dependent names". In both cases VC++ will + accept non-conforming syntax whereas most other compilers will not. Whenever you reference a templated type (and not a templated + value) in a template, you need to prefix it by 'typename'. Whenever your class function refers to a base class member (data or + function), you need to refer to it by "this->", "base_type::", or by placing a "using" statement in your class to +declare that you will be referencing the given base class member.</p> + +<h2> <a name="Iterator_Issues" id="Iterator_Issues"></a>Iterator Issues</h2> +<p>The most important thing to understand about iterators is the concept of iterator types and their designated + properties. In particular, we need to understand the difference between InputIterator, ForwardIterator, + BidirectionalIterator, RandomAccessIterator, and OutputIterator. These differences dictate both how we implement our + algorithms and how we implement our optimizations. Please read the C++ standard for a reasonably well-implemented + description of these iterator types.</p> +<p>Here's an example from EASTL/algorithm.h which demonstrates how we use iterator types to optimize the reverse algorithm +based on the kind of iterator passed to it:</p> +<pre class="code-example">template <class BidirectionalIterator> +inline void reverse_impl(BidirectionalIterator first, BidirectionalIterator last, bidirectional_iterator_tag)<br>{ + for(; (first != last) && (first != --last); ++first) <span class="code-example-comment">// We are not allowed to use operator <, <=, >, >= with</span> + iter_swap(first, last); <span class="code-example-comment">// a generic (bidirectional or otherwise) iterator.</span> +}<br> + +template <typename RandomAccessIterator> +inline void reverse_impl(RandomAccessIterator first, RandomAccessIterator last, random_access_iterator_tag) +{ + for(; first < --last; ++first) <span class="code-example-comment">// With a random access iterator, we can use operator < to more efficiently implement</span> + iter_swap(first, last); <span class="code-example-comment">// this algorithm. A generic iterator doesn't necessarily have an operator < defined.</span> +}<br><br> +template <class BidirectionalIterator> +inline void reverse(BidirectionalIterator first, BidirectionalIterator last) +{ + typedef typename iterator_traits<BidirectionalIterator>::iterator_category IC; + reverse_impl(first, last, IC()); +}</pre> + +<h2> <a name="Exception_Handling" id="Exception_Handling"></a>Exception Handling</h2> +<p>You will notice that EASTL uses try/catch in some places (particularly in containers) and uses + the EASTL_EXCEPTIONS_ENABLED define. For starters, any EASTL code that uses try/catch should always be wrapped + within #if EASTL_EXCEPTIONS_ENABLED (note: #if, not #ifdef).</p> +<p>This is simple enough, but what you may be wondering is how it is that EASTL decides to use try/catch for some sections + of code and not for others. EASTL follows the C++ standard library conventions with respect to exception handling, and + you will see similar exception handling in standard STL. The code that you need to wrap in try/catch is code that can + throw a C++ exception (not to be confused with CPU exception) and needs to have something unwound (or fixed) as a + result. The important thing is that the container be in a valid state after encountering such exceptions. In general +the kinds of things that require such try/catch are:</p> +<ul> +<li>Memory allocation failures (which throw exceptions)</li> +<li>Constructor exceptions</li> +</ul> +<p>Take a look at the cases in EASTL where try/catch is used and see what it is doing.</p> +<h2> <a name="Type_Traits" id="Type_Traits"></a>Type Traits </h2> +<p>EASTL provides a facility called type_traits which is very similar to the type_traits being proposed by the C++ TR1 + (see above). type_traits are useful because they tell you about properties of types at compile time. This allows you to + do things such as assert that a data type is scalar or that a data type is const. The way we put them to use in EASTL + is to take advantage of them to implement different pathways for functions based on types. For example, we can copy a + contiguous array of scalars much faster via memcpy than we can via a for loop, though we could not safely employ the + for loop for a non-trivial C++ class.</p> +<p>As mentioned in the GeneralOptimizations section below, EASTL should take advantage of type_traits information to the +extent possible to achive maximum effiiciency.</p> +<h2> <a name="General_Optimizations" id="General_Optimizations"></a>General +Optimizations</h2> +<p>One of the primary goals of EASTL is to achieve the highest possible efficiency. In cases where EASTL functionality + overlaps standard C++ STL functionality, standard STL implementations provided by compiler vendors are a benchmark upon + which EASTL strives to beat. Indeed EASTL is more efficient than all other current STL implementations (with some + exception in the case of some Metrowerks STL facilities). Here we list some of the things to look for when considering + optimization of EASTL code These items can be considered general optimization suggestions for any code, but this +particular list applies to EASTL:</p> +<ul> +<li>Take advantage of type_traits to the extent possible (e.g. to use memcpy to move data instead of a for loop when +possible).</li> +<li>Take advantage of iterator types to the extent possible.</li> +<li>Take advantage of the compiler's expectation that if statements are expected to evaluate as true and for loop +conditions are expected to evaluate as false.</li> +<li>Make inline-friendly code. This often means avoiding temporaries to the extent possible.</li> +<li>Minimize branching (i.e. minimize 'if' statements). Where branching is used, make it so that 'if' statements +execute as true.</li> +<li>Use EASTL_LIKELY/EASTL_UNLIKELY to give branch hints to the compiler when you are confident it will be +beneficial.</li> +<li>Use restricted pointers (EABase's EA_RESTRICT or various compiler-specific versions of __restrict).</li> +<li>Compare unsigned values to < max instead of comparing signed values to >= 0 && < max.</li> +<li>Employ power of 2 integer math instead of math with any kind of integer.</li> +<li>Use template specialization where possible to implement improved functionality.</li> +<li>Avoid function calls when the call does something trivial. This improves debug build speed (which matters) and +sometimes release build speed as well, though sometimes makes the code intent less clear. A comment next to the code +saying what call it is replacing makes the intent clear without sacrificing performance.</li> +</ul> +<h2><a name="Unit_Tests" id="Unit_Tests"></a>Unit Tests</h2> +<p>Writing robust templated containers and algorithms is difficult or impossible without a heavy unit test suite in place. + EASTL has a pretty extensive set of unit tests for all containers and algorithms. While the successful automated unit + testing of shipping application programs may be a difficult thing to pull off, unit testing of libraries such as this + is of huge importance and cannot be understated. </p> +<ul> +<li>When making a new unit test, start by copying one of the existing unit tests and follow its conventions.</li> +<li>Test containers of both scalars and classes.</li> +<li>Test algorithms on both container iterators (e.g. vector.begin()) and pointer iterators (e.g. int*).</li> +<li>Make sure that algorithm or container member functions which take iterators work with the type of iterator they +claim to (InputIterator, ForwardIterator, BidirectionalIterator, RandomAccessIterator). </li> +<li>Test for const-correctness. If a user is allowed to modify something that is supposed to be const, silent errors +can go undetected.</li> +<li>Make sure that unit tests cover all functions and all pathways of the tested code. This means that in writing the +unit test you need to look at the source code to understand all the pathways.</li> +<li>Consider using a random number generator (one is provided in the test library) to do 'monkey' testing whereby +unexpected input is given to a module being tested. When doing so, make sure you seed the generator in a way that +problems can be reproduced.</li> +<li>While we avoid macros in EASTL user code, macros to assist in unit tests aren't considered a problem. However, +consider that a number of macros could be replaced by templated functions and thus be easier to work with.</li> +<li>Unit tests don't need to be efficient; feel free to take up all the CPU power and time you need to test a module +sufficiently.</li> +<li>EASTL containers are not thread-safe, by design. Thus there is no need to do multithreading tests as long as you +stay away from the usage of static and global variables.</li> +<li>Unit tests must succeed with no memory leaks and of course no memory corruption. The heap system should be +configured to test for this, and heap validation functions are available to the unit tests while in the middle of +runs.</li> +</ul> + +<h2><a name="Things_to_Keep_in_Mind" id="Things_to_Keep_in_Mind"></a>Things to Keep in Mind</h2> +<ul> +<li>When referring to EASTL functions and types from EASTL code, make sure to preface the type with the EASTL +namespace. If you don't do this you can get collisions due to the compiler not knowing if it should use the EASTL +namespace or the namespace of the templated type for the function or type.</li> +<li>Newly constructed empty containers do no memory allocation. Some STL and other container libraries allocate an +initial node from the class memory allocator. EASTL containers by design never do this. If a container needs an +initial node, that node should be made part of the container itself or be a static empty node object.</li> +<li>Empty containers (new or otherwise) contain no constructed objects, including those that might be in an 'end' node. +Similarly, no user object (e.g. of type T) should be constructed unless required by the design and unless documented in +the cotainer/algorithm contract. </li> +<li>When creating a new container class, it's best to copy from an existing similar class to the extent possible. This +helps keep the library consistent and resolves subtle problems that can happen in the construction of containers.</li> +<li>Be very careful about tweaking the code. It's easy to think (for example) that a > could be switch to a >= +where instead it is a big deal. Just about every line of code in EASTL has been thought through and has a purpose. Unit +tests may or may not currently test every bit of EASTL, so you can't necessarily rely on them to give you 100% +confidence in changes. If you are not sure about something, contact the original author and he will tell you for +sure.</li> +<li>Algorithm templates always work with iterators and not containers. A given container may of course implement an +optimized form or an algorithm itself.</li> +<li>Make sure everything is heavily unit tested. If somebody finds a bug, fix the bug and make a unit test to make sure +the bug doesn't happen again.</li> +<li>It's easy to get iterator categories confused or forgotten while implementing algorithms and containers.</li> +<li>Watch out for the strictness of GCC 3.4+. There is a bit of syntax — especially related to templates — that other +compilers accept but GCC 3.4+ will not.</li> +<li>Don't forget to update the config.h EASTL_VERSION define before publishing.</li> +<li>The vector and string classes define iterator to be T*. We want to always leave this so — at least in release +builds — as this gives some algorithms an advantage that optimizers cannot get around.</li> +</ul> +<hr style="width: 100%; height: 2px;"> +<br> +<br> +<br> +<br> +<br> +</body> +</html> |