X-Git-Url: https://oss.titaniummirror.com/gitweb?a=blobdiff_plain;f=libstdc%2B%2B-v3%2Fdocs%2Fhtml%2F17_intro%2FDESIGN;fp=libstdc%2B%2B-v3%2Fdocs%2Fhtml%2F17_intro%2FDESIGN;h=0000000000000000000000000000000000000000;hb=6fed43773c9b0ce596dca5686f37ac3fc0fa11c0;hp=5af3d9aed3be4442e4cf038fbee6acdca55e6b51;hpb=27b11d56b743098deb193d510b337ba22dc52e5c;p=msp430-gcc.git diff --git a/libstdc++-v3/docs/html/17_intro/DESIGN b/libstdc++-v3/docs/html/17_intro/DESIGN deleted file mode 100644 index 5af3d9ae..00000000 --- a/libstdc++-v3/docs/html/17_intro/DESIGN +++ /dev/null @@ -1,859 +0,0 @@ - -Standard C++ Library Design Document ------------------------------------- - -This is an overview of libstdc++-v3, with particular attention -to projects to be done and how they fit into the whole. - -The Library ------------ - -This paper is covers two major areas: - - - Features and policies not mentioned in the standard that - the quality of the library implementation depends on, including - extensions and "implementation-defined" features; - - - Plans for required but unimplemented library features and - optimizations to them. - -Overhead --------- - -The standard defines a large library, much larger than the standard -C library. A naive implementation would suffer substantial overhead -in compile time, executable size, and speed, rendering it unusable -in many (particularly embedded) applications. The alternative demands -care in construction, and some compiler support, but there is no -need for library subsets. - -What are the sources of this overhead? There are four main causes: - - - The library is specified almost entirely as templates, which - with current compilers must be included in-line, resulting in - very slow builds as tens or hundreds of thousands of lines - of function definitions are read for each user source file. - Indeed, the entire SGI STL, as well as the dos Reis valarray, - are provided purely as header files, largely for simplicity in - porting. Iostream/locale is (or will be) as large again. - - - The library is very flexible, specifying a multitude of hooks - where users can insert their own code in place of defaults. - When these hooks are not used, any time and code expended to - support that flexibility is wasted. - - - Templates are often described as causing to "code bloat". In - practice, this refers (when it refers to anything real) to several - independent processes. First, when a class template is manually - instantiated in its entirely, current compilers place the definitions - for all members in a single object file, so that a program linking - to one member gets definitions of all. Second, template functions - which do not actually depend on the template argument are, under - current compilers, generated anew for each instantiation, rather - than being shared with other instantiations. Third, some of the - flexibility mentioned above comes from virtual functions (both in - regular classes and template classes) which current linkers add - to the executable file even when they manifestly cannot be called. - - - The library is specified to use a language feature, exceptions, - which in the current gcc compiler ABI imposes a run time and - code space cost to handle the possibility of exceptions even when - they are not used. Under the new ABI (accessed with -fnew-abi), - there is a space overhead and a small reduction in code efficiency - resulting from lost optimization opportunities associated with - non-local branches associated with exceptions. - -What can be done to eliminate this overhead? A variety of coding -techniques, and compiler, linker and library improvements and -extensions may be used, as covered below. Most are not difficult, -and some are already implemented in varying degrees. - -Overhead: Compilation Time --------------------------- - -Providing "ready-instantiated" template code in object code archives -allows us to avoid generating and optimizing template instantiations -in each compilation unit which uses them. However, the number of such -instantiations that are useful to provide is limited, and anyway this -is not enough, by itself, to minimize compilation time. In particular, -it does not reduce time spent parsing conforming headers. - -Quicker header parsing will depend on library extensions and compiler -improvements. One approach is some variation on the techniques -previously marketed as "pre-compiled headers", now standardized as -support for the "export" keyword. "Exported" template definitions -can be placed (once) in a "repository" -- really just a library, but -of template definitions rather than object code -- to be drawn upon -at link time when an instantiation is needed, rather than placed in -header files to be parsed along with every compilation unit. - -Until "export" is implemented we can put some of the lengthy template -definitions in #if guards or alternative headers so that users can skip -over the the full definitions when they need only the ready-instantiated -specializations. - -To be precise, this means that certain headers which define -templates which users normally use only for certain arguments -can be instrumented to avoid exposing the template definitions -to the compiler unless a macro is defined. For example, in -, we might have: - - template class basic_string { - ... // member declarations - }; - ... // operator declarations - - #ifdef _STRICT_ISO_ - # if _G_NO_TEMPLATE_EXPORT - # include // headers needed by definitions - # ... - # include // member and global template definitions. - # endif - #endif - -Users who compile without specifying a strict-ISO-conforming flag -would not see many of the template definitions they now see, and rely -instead on ready-instantiated specializations in the library. This -technique would be useful for the following substantial components: -string, locale/iostreams, valarray. It would *not* be useful or -usable with the following: containers, algorithms, iterators, -allocator. Since these constitute a large (though decreasing) -fraction of the library, the benefit the technique offers is -limited. - -The language specifies the semantics of the "export" keyword, but -the gcc compiler does not yet support it. When it does, problems -with large template inclusions can largely disappear, given some -minor library reorganization, along with the need for the apparatus -described above. - -Overhead: Flexibility Cost --------------------------- - -The library offers many places where users can specify operations -to be performed by the library in place of defaults. Sometimes -this seems to require that the library use a more-roundabout, and -possibly slower, way to accomplish the default requirements than -would be used otherwise. - -The primary protection against this overhead is thorough compiler -optimization, to crush out layers of inline function interfaces. -Kuck & Associates has demonstrated the practicality of this kind -of optimization. - -The second line of defense against this overhead is explicit -specialization. By defining helper function templates, and writing -specialized code for the default case, overhead can be eliminated -for that case without sacrificing flexibility. This takes full -advantage of any ability of the optimizer to crush out degenerate -code. - -The library specifies many virtual functions which current linkers -load even when they cannot be called. Some minor improvements to the -compiler and to ld would eliminate any such overhead by simply -omitting virtual functions that the complete program does not call. -A prototype of this work has already been done. For targets where -GNU ld is not used, a "pre-linker" could do the same job. - -The main areas in the standard interface where user flexibility -can result in overhead are: - - - Allocators: Containers are specified to use user-definable - allocator types and objects, making tuning for the container - characteristics tricky. - - - Locales: the standard specifies locale objects used to implement - iostream operations, involving many virtual functions which use - streambuf iterators. - - - Algorithms and containers: these may be instantiated on any type, - frequently duplicating code for identical operations. - - - Iostreams and strings: users are permitted to use these on their - own types, and specify the operations the stream must use on these - types. - -Note that these sources of overhead are _avoidable_. The techniques -to avoid them are covered below. - -Code Bloat ----------- - -In the SGI STL, and in some other headers, many of the templates -are defined "inline" -- either explicitly or by their placement -in class definitions -- which should not be inline. This is a -source of code bloat. Matt had remarked that he was relying on -the compiler to recognize what was too big to benefit from inlining, -and generate it out-of-line automatically. However, this also can -result in code bloat except where the linker can eliminate the extra -copies. - -Fixing these cases will require an audit of all inline functions -defined in the library to determine which merit inlining, and moving -the rest out of line. This is an issue mainly in chapters 23, 25, and -27. Of course it can be done incrementally, and we should generally -accept patches that move large functions out of line and into ".tcc" -files, which can later be pulled into a repository. Compiler/linker -improvements to recognize very large inline functions and move them -out-of-line, but shared among compilation units, could make this -work unnecessary. - -Pre-instantiating template specializations currently produces large -amounts of dead code which bloats statically linked programs. The -current state of the static library, libstdc++.a, is intolerable on -this account, and will fuel further confused speculation about a need -for a library "subset". A compiler improvement that treats each -instantiated function as a separate object file, for linking purposes, -would be one solution to this problem. An alternative would be to -split up the manual instantiation files into dozens upon dozens of -little files, each compiled separately, but an abortive attempt at -this was done for and, though it is far from complete, it -is already a nuisance. A better interim solution (just until we have -"export") is badly needed. - -When building a shared library, the current compiler/linker cannot -automatically generate the instantiatiations needed. This creates a -miserable situation; it means any time something is changed in the -library, before a shared library can be built someone must manually -copy the declarations of all templates that are needed by other parts -of the library to an "instantiation" file, and add it to the build -system to be compiled and linked to the library. This process is -readily automated, and should be automated as soon as possible. -Users building their own shared libraries experience identical -frustrations. - -Sharing common aspects of template definitions among instantiations -can radically reduce code bloat. The compiler could help a great -deal here by recognizing when a function depends on nothing about -a template parameter, or only on its size, and giving the resulting -function a link-name "equate" that allows it to be shared with other -instantiations. Implementation code could take advantage of the -capability by factoring out code that does not depend on the template -argument into separate functions to be merged by the compiler. - -Until such a compiler optimization is implemented, much can be done -manually (if tediously) in this direction. One such optimization is -to derive class templates from non-template classes, and move as much -implementation as possible into the base class. Another is to partial- -specialize certain common instantiations, such as vector, to share -code for instantiations on all types T. While these techniques work, -they are far from the complete solution that a compiler improvement -would afford. - -Overhead: Expensive Language Features -------------------------------------- - -The main "expensive" language feature used in the standard library -is exception support, which requires compiling in cleanup code with -static table data to locate it, and linking in library code to use -the table. For small embedded programs the amount of such library -code and table data is assumed by some to be excessive. Under the -"new" ABI this perception is generally exaggerated, although in some -cases it may actually be excessive. - -To implement a library which does not use exceptions directly is -not difficult given minor compiler support (to "turn off" exceptions -and ignore exception constructs), and results in no great library -maintenance difficulties. To be precise, given "-fno-exceptions", -the compiler should treat "try" blocks as ordinary blocks, and -"catch" blocks as dead code to ignore or eliminate. Compiler -support is not strictly necessary, except in the case of "function -try blocks"; otherwise the following macros almost suffice: - - #define throw(X) - #define try if (true) - #define catch(X) else if (false) - -However, there may be a need to use function try blocks in the -library implementation, and use of macros in this way can make -correct diagnostics impossible. Furthermore, use of this scheme -would require the library to call a function to re-throw exceptions -from a try block. Implementing the above semantics in the compiler -is preferable. - -Given the support above (however implemented) it only remains to -replace code that "throws" with a call to a well-documented "handler" -function in a separate compilation unit which may be replaced by -the user. The main source of exceptions that would be difficult -for users to avoid is memory allocation failures, but users can -define their own memory allocation primitives that never throw. -Otherwise, the complete list of such handlers, and which library -functions may call them, would be needed for users to be able to -implement the necessary substitutes. (Fortunately, they have the -source code.) - -Opportunities -------------- - -The template capabilities of C++ offer enormous opportunities for -optimizing common library operations, well beyond what would be -considered "eliminating overhead". In particular, many operations -done in Glibc with macros that depend on proprietary language -extensions can be implemented in pristine Standard C++. For example, -the chapter 25 algorithms, and even C library functions such as strchr, -can be specialized for the case of static arrays of known (small) size. - -Detailed optimization opportunities are identified below where -the component where they would appear is discussed. Of course new -opportunities will be identified during implementation. - -Unimplemented Required Library Features ---------------------------------------- - -The standard specifies hundreds of components, grouped broadly by -chapter. These are listed in excruciating detail in the CHECKLIST -file. - - 17 general - 18 support - 19 diagnostics - 20 utilities - 21 string - 22 locale - 23 containers - 24 iterators - 25 algorithms - 26 numerics - 27 iostreams - Annex D backward compatibility - -Anyone participating in implementation of the library should obtain -a copy of the standard, ISO 14882. People in the U.S. can obtain an -electronic copy for US$18 from ANSI's web site. Those from other -countries should visit http://www.iso.ch/ to find out the location -of their country's representation in ISO, in order to know who can -sell them a copy. - -The emphasis in the following sections is on unimplemented features -and optimization opportunities. - -Chapter 17 General -------------------- - -Chapter 17 concerns overall library requirements. - -The standard doesn't mention threads. A multi-thread (MT) extension -primarily affects operators new and delete (18), allocator (20), -string (21), locale (22), and iostreams (27). The common underlying -support needed for this is discussed under chapter 20. - -The standard requirements on names from the C headers create a -lot of work, mostly done. Names in the C headers must be visible -in the std:: and sometimes the global namespace; the names in the -two scopes must refer to the same object. More stringent is that -Koenig lookup implies that any types specified as defined in std:: -really are defined in std::. Names optionally implemented as -macros in C cannot be macros in C++. (An overview may be read at -). The scripts "inclosure" -and "mkcshadow", and the directories shadow/ and cshadow/, are the -beginning of an effort to conform in this area. - -A correct conforming definition of C header names based on underlying -C library headers, and practical linking of conforming namespaced -customer code with third-party C libraries depends ultimately on -an ABI change, allowing namespaced C type names to be mangled into -type names as if they were global, somewhat as C function names in a -namespace, or C++ global variable names, are left unmangled. Perhaps -another "extern" mode, such as 'extern "C-global"' would be an -appropriate place for such type definitions. Such a type would -affect mangling as follows: - - namespace A { - struct X {}; - extern "C-global" { // or maybe just 'extern "C"' - struct Y {}; - }; - } - void f(A::X*); // mangles to f__FPQ21A1X - void f(A::Y*); // mangles to f__FP1Y - -(It may be that this is really the appropriate semantics for regular -'extern "C"', and 'extern "C-global"', as an extension, would not be -necessary.) This would allow functions declared in non-standard C headers -(and thus fixable by neither us nor users) to link properly with functions -declared using C types defined in properly-namespaced headers. The -problem this solves is that C headers (which C++ programmers do persist -in using) frequently forward-declare C struct tags without including -the header where the type is defined, as in - - struct tm; - void munge(tm*); - -Without some compiler accommodation, munge cannot be called by correct -C++ code using a pointer to a correctly-scoped tm* value. - -The current C headers use the preprocessor extension "#include_next", -which the compiler complains about when run "-pedantic". -(Incidentally, it appears that "-fpedantic" is currently ignored, -probably a bug.) The solution in the C compiler is to use -"-isystem" rather than "-I", but unfortunately in g++ this seems -also to wrap the whole header in an 'extern "C"' block, so it's -unusable for C++ headers. The correct solution appears to be to -allow the various special include-directory options, if not given -an argument, to affect subsequent include-directory options additively, -so that if one said - - -pedantic -iprefix $(prefix) \ - -idirafter -ino-pedantic -ino-extern-c -iwithprefix -I g++-v3 \ - -iwithprefix -I g++-v3/ext - -the compiler would search $(prefix)/g++-v3 and not report -pedantic warnings for files found there, but treat files in -$(prefix)/g++-v3/ext pedantically. (The undocumented semantics -of "-isystem" in g++ stink. Can they be rescinded? If not it -must be replaced with something more rationally behaved.) - -All the C headers need the treatment above; in the standard these -headers are mentioned in various chapters. Below, I have only -mentioned those that present interesting implementation issues. - -The components identified as "mostly complete", below, have not been -audited for conformance. In many cases where the library passes -conformance tests we have non-conforming extensions that must be -wrapped in #if guards for "pedantic" use, and in some cases renamed -in a conforming way for continued use in the implementation regardless -of conformance flags. - -The STL portion of the library still depends on a header -stl/bits/stl_config.h full of #ifdef clauses. This apparatus -should be replaced with autoconf/automake machinery. - -The SGI STL defines a type_traits<> template, specialized for -many types in their code including the built-in numeric and -pointer types and some library types, to direct optimizations of -standard functions. The SGI compiler has been extended to generate -specializations of this template automatically for user types, -so that use of STL templates on user types can take advantage of -these optimizations. Specializations for other, non-STL, types -would make more optimizations possible, but extending the gcc -compiler in the same way would be much better. Probably the next -round of standardization will ratify this, but probably with -changes, so it probably should be renamed to place it in the -implementation namespace. - -The SGI STL also defines a large number of extensions visible in -standard headers. (Other extensions that appear in separate headers -have been sequestered in subdirectories ext/ and backward/.) All -these extensions should be moved to other headers where possible, -and in any case wrapped in a namespace (not std!), and (where kept -in a standard header) girded about with macro guards. Some cannot be -moved out of standard headers because they are used to implement -standard features. The canonical method for accommodating these -is to use a protected name, aliased in macro guards to a user-space -name. Unfortunately C++ offers no satisfactory template typedef -mechanism, so very ad-hoc and unsatisfactory aliasing must be used -instead. - -Implementation of a template typedef mechanism should have the highest -priority among possible extensions, on the same level as implementation -of the template "export" feature. - -Chapter 18 Language support ----------------------------- - -Headers: -C headers: - (also 21, 25, 26) - -This defines the built-in exceptions, rtti, numeric_limits<>, -operator new and delete. Much of this is provided by the -compiler in its static runtime library. - -Work to do includes defining numeric_limits<> specializations in -separate files for all target architectures. Values for integer types -except for bool and wchar_t are readily obtained from the C header -, but values for the remaining numeric types (bool, wchar_t, -float, double, long double) must be entered manually. This is -largely dog work except for those members whose values are not -easily deduced from available documentation. Also, this involves -some work in target configuration to identify the correct choice of -file to build against and to install. - -The definitions of the various operators new and delete must be -made thread-safe, which depends on a portable exclusion mechanism, -discussed under chapter 20. Of course there is always plenty of -room for improvements to the speed of operators new and delete. - -, in Glibc, defines some macros that gcc does not allow to -be wrapped into an inline function. Probably this header will demand -attention whenever a new target is chosen. The functions atexit(), -exit(), and abort() in cstdlib have different semantics in C++, so -must be re-implemented for C++. - -Chapter 19 Diagnostics ------------------------ - -Headers: -C headers: - -This defines the standard exception objects, which are "mostly complete". -Cygnus has a version, and now SGI provides a slightly different one. -It makes little difference which we use. - -The C global name "errno", which C allows to be a variable or a macro, -is required in C++ to be a macro. For MT it must typically result in -a function call. - -Chapter 20 Utilities ---------------------- -Headers: -C header: (also in 18) - -SGI STL provides "mostly complete" versions of all the components -defined in this chapter. However, the auto_ptr<> implementation -is known to be wrong. Furthermore, the standard definition of it -is known to be unimplementable as written. A minor change to the -standard would fix it, and auto_ptr<> should be adjusted to match. - -Multi-threading affects the allocator implementation, and there must -be configuration/installation choices for different users' MT -requirements. Anyway, users will want to tune allocator options -to support different target conditions, MT or no. - -The primitives used for MT implementation should be exposed, as an -extension, for users' own work. We need cross-CPU "mutex" support, -multi-processor shared-memory atomic integer operations, and single- -processor uninterruptible integer operations, and all three configurable -to be stubbed out for non-MT use, or to use an appropriately-loaded -dynamic library for the actual runtime environment, or statically -compiled in for cases where the target architecture is known. - -Chapter 21 String ------------------- -Headers: -C headers: (also in 27) - (also in 18, 25, 26) - -We have "mostly-complete" char_traits<> implementations. Many of the -char_traits operations might be optimized further using existing -proprietary language extensions. - -We have a "mostly-complete" basic_string<> implementation. The work -to manually instantiate char and wchar_t specializations in object -files to improve link-time behavior is extremely unsatisfactory, -literally tripling library-build time with no commensurate improvement -in static program link sizes. It must be redone. (Similar work is -needed for some components in chapters 22 and 27.) - -Other work needed for strings is MT-safety, as discussed under the -chapter 20 heading. - -The standard C type mbstate_t from and used in char_traits<> -must be different in C++ than in C, because in C++ the default constructor -value mbstate_t() must be the "base" or "ground" sequence state. -(According to the likely resolution of a recently raised Core issue, -this may become unnecessary. However, there are other reasons to -use a state type not as limited as whatever the C library provides.) -If we might want to provide conversions from (e.g.) internally- -represented EUC-wide to externally-represented Unicode, or vice- -versa, the mbstate_t we choose will need to be more accommodating -than what might be provided by an underlying C library. - -There remain some basic_string template-member functions which do -not overload properly with their non-template brethren. The infamous -hack akin to what was done in vector<> is needed, to conform to -23.1.1 para 10. The CHECKLIST items for basic_string marked 'X', -or incomplete, are so marked for this reason. - -Replacing the string iterators, which currently are simple character -pointers, with class objects would greatly increase the safety of the -client interface, and also permit a "debug" mode in which range, -ownership, and validity are rigorously checked. The current use of -raw pointers as string iterators is evil. vector<> iterators need the -same treatment. Note that the current implementation freely mixes -pointers and iterators, and that must be fixed before safer iterators -can be introduced. - -Some of the functions in are different from the C version. -generally overloaded on const and non-const argument pointers. For -example, in strchr is overloaded. The functions isupper -etc. in typically implemented as macros in C are functions -in C++, because they are overloaded with others of the same name -defined in . - -Many of the functions required in and cannot be -implemented using underlying C facilities on intended targets because -such facilities only partly exist. - -Chapter 22 Locale ------------------- -Headers: -C headers: - -We have a "mostly complete" class locale, with the exception of -code for constructing, and handling the names of, named locales. -The ways that locales are named (particularly when categories -(e.g. LC_TIME, LC_COLLATE) are different) varies among all target -environments. This code must be written in various versions and -chosen by configuration parameters. - -Members of many of the facets defined in are stubs. Generally, -there are two sets of facets: the base class facets (which are supposed -to implement the "C" locale) and the "byname" facets, which are supposed -to read files to determine their behavior. The base ctype<>, collate<>, -and numpunct<> facets are "mostly complete", except that the table of -bitmask values used for "is" operations, and corresponding mask values, -are still defined in libio and just included/linked. (We will need to -implement these tables independently, soon, but should take advantage -of libio where possible.) The num_put<>::put members for integer types -are "mostly complete". - -A complete list of what has and has not been implemented may be -found in CHECKLIST. However, note that the current definition of -codecvt is wrong. It should simply write -out the raw bytes representing the wide characters, rather than -trying to convert each to a corresponding single "char" value. - -Some of the facets are more important than others. Specifically, -the members of ctype<>, numpunct<>, num_put<>, and num_get<> facets -are used by other library facilities defined in , , -and , and the codecvt<> facet is used by basic_filebuf<> -in , so a conforming iostream implementation depends on -these. - -The "long long" type eventually must be supported, but code mentioning -it should be wrapped in #if guards to allow pedantic-mode compiling. - -Performance of num_put<> and num_get<> depend critically on -caching computed values in ios_base objects, and on extensions -to the interface with streambufs. - -Specifically: retrieving a copy of the locale object, extracting -the needed facets, and gathering data from them, for each call to -(e.g.) operator<< would be prohibitively slow. To cache format -data for use by num_put<> and num_get<> we have a _Format_cache<> -object stored in the ios_base::pword() array. This is constructed -and initialized lazily, and is organized purely for utility. It -is discarded when a new locale with different facets is imbued. - -Using only the public interfaces of the iterator arguments to the -facet functions would limit performance by forbidding "vector-style" -character operations. The streambuf iterator optimizations are -described under chapter 24, but facets can also bypass the streambuf -iterators via explicit specializations and operate directly on the -streambufs, and use extended interfaces to get direct access to the -streambuf internal buffer arrays. These extensions are mentioned -under chapter 27. These optimizations are particularly important -for input parsing. - -Unused virtual members of locale facets can be omitted, as mentioned -above, by a smart linker. - -Chapter 23 Containers ----------------------- -Headers: - -All the components in chapter 23 are implemented in the SGI STL. -They are "mostly complete"; they include a large number of -nonconforming extensions which must be wrapped. Some of these -are used internally and must be renamed or duplicated. - -The SGI components are optimized for large-memory environments. For -embedded targets, different criteria might be more appropriate. Users -will want to be able to tune this behavior. We should provide -ways for users to compile the library with different memory usage -characteristics. - -A lot more work is needed on factoring out common code from different -specializations to reduce code size here and in chapter 25. The -easiest fix for this would be a compiler/ABI improvement that allows -the compiler to recognize when a specialization depends only on the -size (or other gross quality) of a template argument, and allow the -linker to share the code with similar specializations. In its -absence, many of the algorithms and containers can be partial- -specialized, at least for the case of pointers, but this only solves -a small part of the problem. Use of a type_traits-style template -allows a few more optimization opportunities, more if the compiler -can generate the specializations automatically. - -As an optimization, containers can specialize on the default allocator -and bypass it, or take advantage of details of its implementation -after it has been improved upon. - -Replacing the vector iterators, which currently are simple element -pointers, with class objects would greatly increase the safety of the -client interface, and also permit a "debug" mode in which range, -ownership, and validity are rigorously checked. The current use of -pointers for iterators is evil. - -As mentioned for chapter 24, the deque iterator is a good example of -an opportunity to implement a "staged" iterator that would benefit -from specializations of some algorithms. - -Chapter 24 Iterators ---------------------- -Headers: - -Standard iterators are "mostly complete", with the exception of -the stream iterators, which are not yet templatized on the -stream type. Also, the base class template iterator<> appears -to be wrong, so everything derived from it must also be wrong, -currently. - -The streambuf iterators (currently located in stl/bits/std_iterator.h, -but should be under bits/) can be rewritten to take advantage of -friendship with the streambuf implementation. - -Matt Austern has identified opportunities where certain iterator -types, particularly including streambuf iterators and deque -iterators, have a "two-stage" quality, such that an intermediate -limit can be checked much more quickly than the true limit on -range operations. If identified with a member of iterator_traits, -algorithms may be specialized for this case. Of course the -iterators that have this quality can be identified by specializing -a traits class. - -Many of the algorithms must be specialized for the streambuf -iterators, to take advantage of block-mode operations, in order -to allow iostream/locale operations' performance not to suffer. -It may be that they could be treated as staged iterators and -take advantage of those optimizations. - -Chapter 25 Algorithms ----------------------- -Headers: -C headers: (also in 18, 21, 26)) - -The algorithms are "mostly complete". As mentioned above, they -are optimized for speed at the expense of code and data size. - -Specializations of many of the algorithms for non-STL types would -give performance improvements, but we must use great care not to -interfere with fragile template overloading semantics for the -standard interfaces. Conventionally the standard function template -interface is an inline which delegates to a non-standard function -which is then overloaded (this is already done in many places in -the library). Particularly appealing opportunities for the sake of -iostream performance are for copy and find applied to streambuf -iterators or (as noted elsewhere) for staged iterators, of which -the streambuf iterators are a good example. - -The bsearch and qsort functions cannot be overloaded properly as -required by the standard because gcc does not yet allow overloading -on the extern-"C"-ness of a function pointer. - -Chapter 26 Numerics --------------------- -Headers: -C headers: , (also 18, 21, 25) - -Numeric components: Gabriel dos Reis's valarray, Drepper's complex, -and the few algorithms from the STL are "mostly done". Of course -optimization opportunities abound for the numerically literate. It -is not clear whether the valarray implementation really conforms -fully, in the assumptions it makes about aliasing (and lack thereof) -in its arguments. - -The C div() and ldiv() functions are interesting, because they are the -only case where a C library function returns a class object by value. -Since the C++ type div_t must be different from the underlying C type -(which is in the wrong namespace) the underlying functions div() and -ldiv() cannot be re-used efficiently. Fortunately they are trivial to -re-implement. - -Chapter 27 Iostreams ---------------------- -Headers: - -C headers: (also in 21) - -Iostream is currently in a very incomplete state. , , -ios_base, and basic_ios<> are "mostly complete". basic_streambuf<> and -basic_ostream<> are well along, but basic_istream<> has had little work -done. The standard stream objects, and have been -started; basic_filebuf<> "write" functions have been implemented just -enough to do "hello, world". - -Most of the istream and ostream operators << and >> (with the exception -of the op<<(integer) ones) have not been changed to use locale primitives, -sentry objects, or char_traits members. - -All these templates should be manually instantiated for char and -wchar_t in a way that links only used members into user programs. - -Streambuf is fertile ground for optimization extensions. An extended -interface giving iterator access to its internal buffer would be very -useful for other library components. - -Iostream operations (primarily operators << and >>) can take advantage -of the case where user code has not specified a locale, and bypass locale -operations entirely. The current implementation of op<::put, -for the integer types, demonstrates how they can cache encoding details -from the locale on each operation. There is lots more room for -optimization in this area. - -The definition of the relationship between the standard streams -cout et al. and stdout et al. requires something like a "stdiobuf". -The SGI solution of using double-indirection to actually use a -stdio FILE object for buffering is unsatisfactory, because it -interferes with peephole loop optimizations. - -The header work has begun. stringbuf can benefit from -friendship with basic_string<> and basic_string<>::_Rep to use -those objects directly as buffers, and avoid allocating and making -copies. - -The basic_filebuf<> template is a complex beast. It is specified to -use the locale facet codecvt<> to translate characters between native -files and the locale character encoding. In general this involves -two buffers, one of "char" representing the file and another of -"char_type", for the stream, with codecvt<> translating. The process -is complicated by the variable-length nature of the translation, and -the need to seek to corresponding places in the two representations. -For the case of basic_filebuf, when no translation is needed, -a single buffer suffices. A specialized filebuf can be used to reduce -code space overhead when no locale has been imbued. Matt Austern's -work at SGI will be useful, perhaps directly as a source of code, or -at least as an example to draw on. - -Filebuf, almost uniquely (cf. operator new), depends heavily on -underlying environmental facilities. In current releases iostream -depends fairly heavily on libio constant definitions, but it should -be made independent. It also depends on operating system primitives -for file operations. There is immense room for optimizations using -(e.g.) mmap for reading. The shadow/ directory wraps, besides the -standard C headers, the libio.h and unistd.h headers, for use mainly -by filebuf. These wrappings have not been completed, though there -is scaffolding in place. - -The encapulation of certain C header names presents an -interesting problem. It is possible to define an inline std::fprintf() -implemented in terms of the 'extern "C"' vfprintf(), but there is no -standard vfscanf() to use to implement std::fscanf(). It appears that -vfscanf but be re-implemented in C++ for targets where no vfscanf -extension has been defined. This is interesting in that it seems -to be the only significant case in the C library where this kind of -rewriting is necessary. (Of course Glibc provides the vfscanf() -extension.) (The functions related to exit() must be rewritten -for other reasons.) - - -Annex D -------- -Headers: - -Annex D defines many non-library features, and many minor -modifications to various headers, and a complete header. -It is "mostly done", except that the libstdc++-2 -header has not been adopted into the library, or checked to -verify that it matches the draft in those details that were -clarified by the committee. Certainly it must at least be -moved into the std namespace. - -We still need to wrap all the deprecated features in #if guards -so that pedantic compile modes can detect their use. - -Nonstandard Extensions ----------------------- -Headers: - (etc.) - -User code has come to depend on a variety of nonstandard components -that we must not omit. Much of this code can be adopted from -libstdc++-v2 or from the SGI STL. This particularly includes -, , and various SGI extensions such -as . Many of these are already placed in the -subdirectories ext/ and backward/. (Note that it is better to -include them via "" or "" than -to search the subdirectory itself via a "-I" directive. -