1<?xml version="1.0" encoding="UTF-8" standalone="no"?> 2<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /><title>Design Notes</title><meta name="generator" content="DocBook XSL Stylesheets Vsnapshot" /><meta name="keywords" content="ISO C++, library" /><meta name="keywords" content="ISO C++, runtime, library" /><link rel="home" href="../index.html" title="The GNU C++ Library" /><link rel="up" href="appendix_contributing.html" title="Appendix A. Contributing" /><link rel="prev" href="source_code_style.html" title="Coding Style" /><link rel="next" href="appendix_porting.html" title="Appendix B. Porting and Maintenance" /></head><body><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="3" align="center">Design Notes</th></tr><tr><td width="20%" align="left"><a accesskey="p" href="source_code_style.html">Prev</a> </td><th width="60%" align="center">Appendix A. 3 Contributing 4 5</th><td width="20%" align="right"> <a accesskey="n" href="appendix_porting.html">Next</a></td></tr></table><hr /></div><div class="section"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="contrib.design_notes"></a>Design Notes</h2></div></div></div><p> 6 </p><div class="literallayout"><p><br /> 7<br /> 8 The Library<br /> 9 -----------<br /> 10<br /> 11 This paper is covers two major areas:<br /> 12<br /> 13 - Features and policies not mentioned in the standard that<br /> 14 the quality of the library implementation depends on, including<br /> 15 extensions and "implementation-defined" features;<br /> 16<br /> 17 - Plans for required but unimplemented library features and<br /> 18 optimizations to them.<br /> 19<br /> 20 Overhead<br /> 21 --------<br /> 22<br /> 23 The standard defines a large library, much larger than the standard<br /> 24 C library. A naive implementation would suffer substantial overhead<br /> 25 in compile time, executable size, and speed, rendering it unusable<br /> 26 in many (particularly embedded) applications. The alternative demands<br /> 27 care in construction, and some compiler support, but there is no<br /> 28 need for library subsets.<br /> 29<br /> 30 What are the sources of this overhead? There are four main causes:<br /> 31<br /> 32 - The library is specified almost entirely as templates, which<br /> 33 with current compilers must be included in-line, resulting in<br /> 34 very slow builds as tens or hundreds of thousands of lines<br /> 35 of function definitions are read for each user source file.<br /> 36 Indeed, the entire SGI STL, as well as the dos Reis valarray,<br /> 37 are provided purely as header files, largely for simplicity in<br /> 38 porting. Iostream/locale is (or will be) as large again.<br /> 39<br /> 40 - The library is very flexible, specifying a multitude of hooks<br /> 41 where users can insert their own code in place of defaults.<br /> 42 When these hooks are not used, any time and code expended to<br /> 43 support that flexibility is wasted.<br /> 44<br /> 45 - Templates are often described as causing to "code bloat". In<br /> 46 practice, this refers (when it refers to anything real) to several<br /> 47 independent processes. First, when a class template is manually<br /> 48 instantiated in its entirely, current compilers place the definitions<br /> 49 for all members in a single object file, so that a program linking<br /> 50 to one member gets definitions of all. Second, template functions<br /> 51 which do not actually depend on the template argument are, under<br /> 52 current compilers, generated anew for each instantiation, rather<br /> 53 than being shared with other instantiations. Third, some of the<br /> 54 flexibility mentioned above comes from virtual functions (both in<br /> 55 regular classes and template classes) which current linkers add<br /> 56 to the executable file even when they manifestly cannot be called.<br /> 57<br /> 58 - The library is specified to use a language feature, exceptions,<br /> 59 which in the current gcc compiler ABI imposes a run time and<br /> 60 code space cost to handle the possibility of exceptions even when<br /> 61 they are not used. Under the new ABI (accessed with -fnew-abi),<br /> 62 there is a space overhead and a small reduction in code efficiency<br /> 63 resulting from lost optimization opportunities associated with<br /> 64 non-local branches associated with exceptions.<br /> 65<br /> 66 What can be done to eliminate this overhead? A variety of coding<br /> 67 techniques, and compiler, linker and library improvements and<br /> 68 extensions may be used, as covered below. Most are not difficult,<br /> 69 and some are already implemented in varying degrees.<br /> 70<br /> 71 Overhead: Compilation Time<br /> 72 --------------------------<br /> 73<br /> 74 Providing "ready-instantiated" template code in object code archives<br /> 75 allows us to avoid generating and optimizing template instantiations<br /> 76 in each compilation unit which uses them. However, the number of such<br /> 77 instantiations that are useful to provide is limited, and anyway this<br /> 78 is not enough, by itself, to minimize compilation time. In particular,<br /> 79 it does not reduce time spent parsing conforming headers.<br /> 80<br /> 81 Quicker header parsing will depend on library extensions and compiler<br /> 82 improvements. One approach is some variation on the techniques<br /> 83 previously marketed as "pre-compiled headers", now standardized as<br /> 84 support for the "export" keyword. "Exported" template definitions<br /> 85 can be placed (once) in a "repository" -- really just a library, but<br /> 86 of template definitions rather than object code -- to be drawn upon<br /> 87 at link time when an instantiation is needed, rather than placed in<br /> 88 header files to be parsed along with every compilation unit.<br /> 89<br /> 90 Until "export" is implemented we can put some of the lengthy template<br /> 91 definitions in #if guards or alternative headers so that users can skip<br /> 92 over the full definitions when they need only the ready-instantiated<br /> 93 specializations.<br /> 94<br /> 95 To be precise, this means that certain headers which define<br /> 96 templates which users normally use only for certain arguments<br /> 97 can be instrumented to avoid exposing the template definitions<br /> 98 to the compiler unless a macro is defined. For example, in<br /> 99 <string>, we might have:<br /> 100<br /> 101 template <class _CharT, ... > class basic_string {<br /> 102 ... // member declarations<br /> 103 };<br /> 104 ... // operator declarations<br /> 105<br /> 106 #ifdef _STRICT_ISO_<br /> 107 # if _G_NO_TEMPLATE_EXPORT<br /> 108 # include <bits/std_locale.h> // headers needed by definitions<br /> 109 # ...<br /> 110 # include <bits/string.tcc> // member and global template definitions.<br /> 111 # endif<br /> 112 #endif<br /> 113<br /> 114 Users who compile without specifying a strict-ISO-conforming flag<br /> 115 would not see many of the template definitions they now see, and rely<br /> 116 instead on ready-instantiated specializations in the library. This<br /> 117 technique would be useful for the following substantial components:<br /> 118 string, locale/iostreams, valarray. It would *not* be useful or<br /> 119 usable with the following: containers, algorithms, iterators,<br /> 120 allocator. Since these constitute a large (though decreasing)<br /> 121 fraction of the library, the benefit the technique offers is<br /> 122 limited.<br /> 123<br /> 124 The language specifies the semantics of the "export" keyword, but<br /> 125 the gcc compiler does not yet support it. When it does, problems<br /> 126 with large template inclusions can largely disappear, given some<br /> 127 minor library reorganization, along with the need for the apparatus<br /> 128 described above.<br /> 129<br /> 130 Overhead: Flexibility Cost<br /> 131 --------------------------<br /> 132<br /> 133 The library offers many places where users can specify operations<br /> 134 to be performed by the library in place of defaults. Sometimes<br /> 135 this seems to require that the library use a more-roundabout, and<br /> 136 possibly slower, way to accomplish the default requirements than<br /> 137 would be used otherwise.<br /> 138<br /> 139 The primary protection against this overhead is thorough compiler<br /> 140 optimization, to crush out layers of inline function interfaces.<br /> 141 Kuck & Associates has demonstrated the practicality of this kind<br /> 142 of optimization.<br /> 143<br /> 144 The second line of defense against this overhead is explicit<br /> 145 specialization. By defining helper function templates, and writing<br /> 146 specialized code for the default case, overhead can be eliminated<br /> 147 for that case without sacrificing flexibility. This takes full<br /> 148 advantage of any ability of the optimizer to crush out degenerate<br /> 149 code.<br /> 150<br /> 151 The library specifies many virtual functions which current linkers<br /> 152 load even when they cannot be called. Some minor improvements to the<br /> 153 compiler and to ld would eliminate any such overhead by simply<br /> 154 omitting virtual functions that the complete program does not call.<br /> 155 A prototype of this work has already been done. For targets where<br /> 156 GNU ld is not used, a "pre-linker" could do the same job.<br /> 157<br /> 158 The main areas in the standard interface where user flexibility<br /> 159 can result in overhead are:<br /> 160<br /> 161 - Allocators: Containers are specified to use user-definable<br /> 162 allocator types and objects, making tuning for the container<br /> 163 characteristics tricky.<br /> 164<br /> 165 - Locales: the standard specifies locale objects used to implement<br /> 166 iostream operations, involving many virtual functions which use<br /> 167 streambuf iterators.<br /> 168<br /> 169 - Algorithms and containers: these may be instantiated on any type,<br /> 170 frequently duplicating code for identical operations.<br /> 171<br /> 172 - Iostreams and strings: users are permitted to use these on their<br /> 173 own types, and specify the operations the stream must use on these<br /> 174 types.<br /> 175<br /> 176 Note that these sources of overhead are _avoidable_. The techniques<br /> 177 to avoid them are covered below.<br /> 178<br /> 179 Code Bloat<br /> 180 ----------<br /> 181<br /> 182 In the SGI STL, and in some other headers, many of the templates<br /> 183 are defined "inline" -- either explicitly or by their placement<br /> 184 in class definitions -- which should not be inline. This is a<br /> 185 source of code bloat. Matt had remarked that he was relying on<br /> 186 the compiler to recognize what was too big to benefit from inlining,<br /> 187 and generate it out-of-line automatically. However, this also can<br /> 188 result in code bloat except where the linker can eliminate the extra<br /> 189 copies.<br /> 190<br /> 191 Fixing these cases will require an audit of all inline functions<br /> 192 defined in the library to determine which merit inlining, and moving<br /> 193 the rest out of line. This is an issue mainly in clauses 23, 25, and<br /> 194 27. Of course it can be done incrementally, and we should generally<br /> 195 accept patches that move large functions out of line and into ".tcc"<br /> 196 files, which can later be pulled into a repository. Compiler/linker<br /> 197 improvements to recognize very large inline functions and move them<br /> 198 out-of-line, but shared among compilation units, could make this<br /> 199 work unnecessary.<br /> 200<br /> 201 Pre-instantiating template specializations currently produces large<br /> 202 amounts of dead code which bloats statically linked programs. The<br /> 203 current state of the static library, libstdc++.a, is intolerable on<br /> 204 this account, and will fuel further confused speculation about a need<br /> 205 for a library "subset". A compiler improvement that treats each<br /> 206 instantiated function as a separate object file, for linking purposes,<br /> 207 would be one solution to this problem. An alternative would be to<br /> 208 split up the manual instantiation files into dozens upon dozens of<br /> 209 little files, each compiled separately, but an abortive attempt at<br /> 210 this was done for <string> and, though it is far from complete, it<br /> 211 is already a nuisance. A better interim solution (just until we have<br /> 212 "export") is badly needed.<br /> 213<br /> 214 When building a shared library, the current compiler/linker cannot<br /> 215 automatically generate the instantiations needed. This creates a<br /> 216 miserable situation; it means any time something is changed in the<br /> 217 library, before a shared library can be built someone must manually<br /> 218 copy the declarations of all templates that are needed by other parts<br /> 219 of the library to an "instantiation" file, and add it to the build<br /> 220 system to be compiled and linked to the library. This process is<br /> 221 readily automated, and should be automated as soon as possible.<br /> 222 Users building their own shared libraries experience identical<br /> 223 frustrations.<br /> 224<br /> 225 Sharing common aspects of template definitions among instantiations<br /> 226 can radically reduce code bloat. The compiler could help a great<br /> 227 deal here by recognizing when a function depends on nothing about<br /> 228 a template parameter, or only on its size, and giving the resulting<br /> 229 function a link-name "equate" that allows it to be shared with other<br /> 230 instantiations. Implementation code could take advantage of the<br /> 231 capability by factoring out code that does not depend on the template<br /> 232 argument into separate functions to be merged by the compiler.<br /> 233<br /> 234 Until such a compiler optimization is implemented, much can be done<br /> 235 manually (if tediously) in this direction. One such optimization is<br /> 236 to derive class templates from non-template classes, and move as much<br /> 237 implementation as possible into the base class. Another is to partial-<br /> 238 specialize certain common instantiations, such as vector<T*>, to share<br /> 239 code for instantiations on all types T. While these techniques work,<br /> 240 they are far from the complete solution that a compiler improvement<br /> 241 would afford.<br /> 242<br /> 243 Overhead: Expensive Language Features<br /> 244 -------------------------------------<br /> 245<br /> 246 The main "expensive" language feature used in the standard library<br /> 247 is exception support, which requires compiling in cleanup code with<br /> 248 static table data to locate it, and linking in library code to use<br /> 249 the table. For small embedded programs the amount of such library<br /> 250 code and table data is assumed by some to be excessive. Under the<br /> 251 "new" ABI this perception is generally exaggerated, although in some<br /> 252 cases it may actually be excessive.<br /> 253<br /> 254 To implement a library which does not use exceptions directly is<br /> 255 not difficult given minor compiler support (to "turn off" exceptions<br /> 256 and ignore exception constructs), and results in no great library<br /> 257 maintenance difficulties. To be precise, given "-fno-exceptions",<br /> 258 the compiler should treat "try" blocks as ordinary blocks, and<br /> 259 "catch" blocks as dead code to ignore or eliminate. Compiler<br /> 260 support is not strictly necessary, except in the case of "function<br /> 261 try blocks"; otherwise the following macros almost suffice:<br /> 262<br /> 263 #define throw(X)<br /> 264 #define try if (true)<br /> 265 #define catch(X) else if (false)<br /> 266<br /> 267 However, there may be a need to use function try blocks in the<br /> 268 library implementation, and use of macros in this way can make<br /> 269 correct diagnostics impossible. Furthermore, use of this scheme<br /> 270 would require the library to call a function to re-throw exceptions<br /> 271 from a try block. Implementing the above semantics in the compiler<br /> 272 is preferable.<br /> 273<br /> 274 Given the support above (however implemented) it only remains to<br /> 275 replace code that "throws" with a call to a well-documented "handler"<br /> 276 function in a separate compilation unit which may be replaced by<br /> 277 the user. The main source of exceptions that would be difficult<br /> 278 for users to avoid is memory allocation failures, but users can<br /> 279 define their own memory allocation primitives that never throw.<br /> 280 Otherwise, the complete list of such handlers, and which library<br /> 281 functions may call them, would be needed for users to be able to<br /> 282 implement the necessary substitutes. (Fortunately, they have the<br /> 283 source code.)<br /> 284<br /> 285 Opportunities<br /> 286 -------------<br /> 287<br /> 288 The template capabilities of C++ offer enormous opportunities for<br /> 289 optimizing common library operations, well beyond what would be<br /> 290 considered "eliminating overhead". In particular, many operations<br /> 291 done in Glibc with macros that depend on proprietary language<br /> 292 extensions can be implemented in pristine Standard C++. For example,<br /> 293 the chapter 25 algorithms, and even C library functions such as strchr,<br /> 294 can be specialized for the case of static arrays of known (small) size.<br /> 295<br /> 296 Detailed optimization opportunities are identified below where<br /> 297 the component where they would appear is discussed. Of course new<br /> 298 opportunities will be identified during implementation.<br /> 299<br /> 300 Unimplemented Required Library Features<br /> 301 ---------------------------------------<br /> 302<br /> 303 The standard specifies hundreds of components, grouped broadly by<br /> 304 chapter. These are listed in excruciating detail in the CHECKLIST<br /> 305 file.<br /> 306<br /> 307 17 general<br /> 308 18 support<br /> 309 19 diagnostics<br /> 310 20 utilities<br /> 311 21 string<br /> 312 22 locale<br /> 313 23 containers<br /> 314 24 iterators<br /> 315 25 algorithms<br /> 316 26 numerics<br /> 317 27 iostreams<br /> 318 Annex D backward compatibility<br /> 319<br /> 320 Anyone participating in implementation of the library should obtain<br /> 321 a copy of the standard, ISO 14882. People in the U.S. can obtain an<br /> 322 electronic copy for US$18 from ANSI's web site. Those from other<br /> 323 countries should visit http://www.iso.org/ to find out the location<br /> 324 of their country's representation in ISO, in order to know who can<br /> 325 sell them a copy.<br /> 326<br /> 327 The emphasis in the following sections is on unimplemented features<br /> 328 and optimization opportunities.<br /> 329<br /> 330 Chapter 17 General<br /> 331 -------------------<br /> 332<br /> 333 Chapter 17 concerns overall library requirements.<br /> 334<br /> 335 The standard doesn't mention threads. A multi-thread (MT) extension<br /> 336 primarily affects operators new and delete (18), allocator (20),<br /> 337 string (21), locale (22), and iostreams (27). The common underlying<br /> 338 support needed for this is discussed under chapter 20.<br /> 339<br /> 340 The standard requirements on names from the C headers create a<br /> 341 lot of work, mostly done. Names in the C headers must be visible<br /> 342 in the std:: and sometimes the global namespace; the names in the<br /> 343 two scopes must refer to the same object. More stringent is that<br /> 344 Koenig lookup implies that any types specified as defined in std::<br /> 345 really are defined in std::. Names optionally implemented as<br /> 346 macros in C cannot be macros in C++. (An overview may be read at<br /> 347 <http://www.cantrip.org/cheaders.html>). The scripts "inclosure"<br /> 348 and "mkcshadow", and the directories shadow/ and cshadow/, are the<br /> 349 beginning of an effort to conform in this area.<br /> 350<br /> 351 A correct conforming definition of C header names based on underlying<br /> 352 C library headers, and practical linking of conforming namespaced<br /> 353 customer code with third-party C libraries depends ultimately on<br /> 354 an ABI change, allowing namespaced C type names to be mangled into<br /> 355 type names as if they were global, somewhat as C function names in a<br /> 356 namespace, or C++ global variable names, are left unmangled. Perhaps<br /> 357 another "extern" mode, such as 'extern "C-global"' would be an<br /> 358 appropriate place for such type definitions. Such a type would<br /> 359 affect mangling as follows:<br /> 360<br /> 361 namespace A {<br /> 362 struct X {};<br /> 363 extern "C-global" { // or maybe just 'extern "C"'<br /> 364 struct Y {};<br /> 365 };<br /> 366 }<br /> 367 void f(A::X*); // mangles to f__FPQ21A1X<br /> 368 void f(A::Y*); // mangles to f__FP1Y<br /> 369<br /> 370 (It may be that this is really the appropriate semantics for regular<br /> 371 'extern "C"', and 'extern "C-global"', as an extension, would not be<br /> 372 necessary.) This would allow functions declared in non-standard C headers<br /> 373 (and thus fixable by neither us nor users) to link properly with functions<br /> 374 declared using C types defined in properly-namespaced headers. The<br /> 375 problem this solves is that C headers (which C++ programmers do persist<br /> 376 in using) frequently forward-declare C struct tags without including<br /> 377 the header where the type is defined, as in<br /> 378<br /> 379 struct tm;<br /> 380 void munge(tm*);<br /> 381<br /> 382 Without some compiler accommodation, munge cannot be called by correct<br /> 383 C++ code using a pointer to a correctly-scoped tm* value.<br /> 384<br /> 385 The current C headers use the preprocessor extension "#include_next",<br /> 386 which the compiler complains about when run "-pedantic".<br /> 387 (Incidentally, it appears that "-fpedantic" is currently ignored,<br /> 388 probably a bug.) The solution in the C compiler is to use<br /> 389 "-isystem" rather than "-I", but unfortunately in g++ this seems<br /> 390 also to wrap the whole header in an 'extern "C"' block, so it's<br /> 391 unusable for C++ headers. The correct solution appears to be to<br /> 392 allow the various special include-directory options, if not given<br /> 393 an argument, to affect subsequent include-directory options additively,<br /> 394 so that if one said<br /> 395<br /> 396 -pedantic -iprefix $(prefix) \<br /> 397 -idirafter -ino-pedantic -ino-extern-c -iwithprefix -I g++-v3 \<br /> 398 -iwithprefix -I g++-v3/ext<br /> 399<br /> 400 the compiler would search $(prefix)/g++-v3 and not report<br /> 401 pedantic warnings for files found there, but treat files in<br /> 402 $(prefix)/g++-v3/ext pedantically. (The undocumented semantics<br /> 403 of "-isystem" in g++ stink. Can they be rescinded? If not it<br /> 404 must be replaced with something more rationally behaved.)<br /> 405<br /> 406 All the C headers need the treatment above; in the standard these<br /> 407 headers are mentioned in various clauses. Below, I have only<br /> 408 mentioned those that present interesting implementation issues.<br /> 409<br /> 410 The components identified as "mostly complete", below, have not been<br /> 411 audited for conformance. In many cases where the library passes<br /> 412 conformance tests we have non-conforming extensions that must be<br /> 413 wrapped in #if guards for "pedantic" use, and in some cases renamed<br /> 414 in a conforming way for continued use in the implementation regardless<br /> 415 of conformance flags.<br /> 416<br /> 417 The STL portion of the library still depends on a header<br /> 418 stl/bits/stl_config.h full of #ifdef clauses. This apparatus<br /> 419 should be replaced with autoconf/automake machinery.<br /> 420<br /> 421 The SGI STL defines a type_traits<> template, specialized for<br /> 422 many types in their code including the built-in numeric and<br /> 423 pointer types and some library types, to direct optimizations of<br /> 424 standard functions. The SGI compiler has been extended to generate<br /> 425 specializations of this template automatically for user types,<br /> 426 so that use of STL templates on user types can take advantage of<br /> 427 these optimizations. Specializations for other, non-STL, types<br /> 428 would make more optimizations possible, but extending the gcc<br /> 429 compiler in the same way would be much better. Probably the next<br /> 430 round of standardization will ratify this, but probably with<br /> 431 changes, so it probably should be renamed to place it in the<br /> 432 implementation namespace.<br /> 433<br /> 434 The SGI STL also defines a large number of extensions visible in<br /> 435 standard headers. (Other extensions that appear in separate headers<br /> 436 have been sequestered in subdirectories ext/ and backward/.) All<br /> 437 these extensions should be moved to other headers where possible,<br /> 438 and in any case wrapped in a namespace (not std!), and (where kept<br /> 439 in a standard header) girded about with macro guards. Some cannot be<br /> 440 moved out of standard headers because they are used to implement<br /> 441 standard features. The canonical method for accommodating these<br /> 442 is to use a protected name, aliased in macro guards to a user-space<br /> 443 name. Unfortunately C++ offers no satisfactory template typedef<br /> 444 mechanism, so very ad-hoc and unsatisfactory aliasing must be used<br /> 445 instead.<br /> 446<br /> 447 Implementation of a template typedef mechanism should have the highest<br /> 448 priority among possible extensions, on the same level as implementation<br /> 449 of the template "export" feature.<br /> 450<br /> 451 Chapter 18 Language support<br /> 452 ----------------------------<br /> 453<br /> 454 Headers: <limits> <new> <typeinfo> <exception><br /> 455 C headers: <cstddef> <climits> <cfloat> <cstdarg> <csetjmp><br /> 456 <ctime> <csignal> <cstdlib> (also 21, 25, 26)<br /> 457<br /> 458 This defines the built-in exceptions, rtti, numeric_limits<>,<br /> 459 operator new and delete. Much of this is provided by the<br /> 460 compiler in its static runtime library.<br /> 461<br /> 462 Work to do includes defining numeric_limits<> specializations in<br /> 463 separate files for all target architectures. Values for integer types<br /> 464 except for bool and wchar_t are readily obtained from the C header<br /> 465 <limits.h>, but values for the remaining numeric types (bool, wchar_t,<br /> 466 float, double, long double) must be entered manually. This is<br /> 467 largely dog work except for those members whose values are not<br /> 468 easily deduced from available documentation. Also, this involves<br /> 469 some work in target configuration to identify the correct choice of<br /> 470 file to build against and to install.<br /> 471<br /> 472 The definitions of the various operators new and delete must be<br /> 473 made thread-safe, which depends on a portable exclusion mechanism,<br /> 474 discussed under chapter 20. Of course there is always plenty of<br /> 475 room for improvements to the speed of operators new and delete.<br /> 476<br /> 477 <cstdarg>, in Glibc, defines some macros that gcc does not allow to<br /> 478 be wrapped into an inline function. Probably this header will demand<br /> 479 attention whenever a new target is chosen. The functions atexit(),<br /> 480 exit(), and abort() in cstdlib have different semantics in C++, so<br /> 481 must be re-implemented for C++.<br /> 482<br /> 483 Chapter 19 Diagnostics<br /> 484 -----------------------<br /> 485<br /> 486 Headers: <stdexcept><br /> 487 C headers: <cassert> <cerrno><br /> 488<br /> 489 This defines the standard exception objects, which are "mostly complete".<br /> 490 Cygnus has a version, and now SGI provides a slightly different one.<br /> 491 It makes little difference which we use.<br /> 492<br /> 493 The C global name "errno", which C allows to be a variable or a macro,<br /> 494 is required in C++ to be a macro. For MT it must typically result in<br /> 495 a function call.<br /> 496<br /> 497 Chapter 20 Utilities<br /> 498 ---------------------<br /> 499 Headers: <utility> <functional> <memory><br /> 500 C header: <ctime> (also in 18)<br /> 501<br /> 502 SGI STL provides "mostly complete" versions of all the components<br /> 503 defined in this chapter. However, the auto_ptr<> implementation<br /> 504 is known to be wrong. Furthermore, the standard definition of it<br /> 505 is known to be unimplementable as written. A minor change to the<br /> 506 standard would fix it, and auto_ptr<> should be adjusted to match.<br /> 507<br /> 508 Multi-threading affects the allocator implementation, and there must<br /> 509 be configuration/installation choices for different users' MT<br /> 510 requirements. Anyway, users will want to tune allocator options<br /> 511 to support different target conditions, MT or no.<br /> 512<br /> 513 The primitives used for MT implementation should be exposed, as an<br /> 514 extension, for users' own work. We need cross-CPU "mutex" support,<br /> 515 multi-processor shared-memory atomic integer operations, and single-<br /> 516 processor uninterruptible integer operations, and all three configurable<br /> 517 to be stubbed out for non-MT use, or to use an appropriately-loaded<br /> 518 dynamic library for the actual runtime environment, or statically<br /> 519 compiled in for cases where the target architecture is known.<br /> 520<br /> 521 Chapter 21 String<br /> 522 ------------------<br /> 523 Headers: <string><br /> 524 C headers: <cctype> <cwctype> <cstring> <cwchar> (also in 27)<br /> 525 <cstdlib> (also in 18, 25, 26)<br /> 526<br /> 527 We have "mostly-complete" char_traits<> implementations. Many of the<br /> 528 char_traits<char> operations might be optimized further using existing<br /> 529 proprietary language extensions.<br /> 530<br /> 531 We have a "mostly-complete" basic_string<> implementation. The work<br /> 532 to manually instantiate char and wchar_t specializations in object<br /> 533 files to improve link-time behavior is extremely unsatisfactory,<br /> 534 literally tripling library-build time with no commensurate improvement<br /> 535 in static program link sizes. It must be redone. (Similar work is<br /> 536 needed for some components in clauses 22 and 27.)<br /> 537<br /> 538 Other work needed for strings is MT-safety, as discussed under the<br /> 539 chapter 20 heading.<br /> 540<br /> 541 The standard C type mbstate_t from <cwchar> and used in char_traits<><br /> 542 must be different in C++ than in C, because in C++ the default constructor<br /> 543 value mbstate_t() must be the "base" or "ground" sequence state.<br /> 544 (According to the likely resolution of a recently raised Core issue,<br /> 545 this may become unnecessary. However, there are other reasons to<br /> 546 use a state type not as limited as whatever the C library provides.)<br /> 547 If we might want to provide conversions from (e.g.) internally-<br /> 548 represented EUC-wide to externally-represented Unicode, or vice-<br /> 549 versa, the mbstate_t we choose will need to be more accommodating<br /> 550 than what might be provided by an underlying C library.<br /> 551<br /> 552 There remain some basic_string template-member functions which do<br /> 553 not overload properly with their non-template brethren. The infamous<br /> 554 hack akin to what was done in vector<> is needed, to conform to<br /> 555 23.1.1 para 10. The CHECKLIST items for basic_string marked 'X',<br /> 556 or incomplete, are so marked for this reason.<br /> 557<br /> 558 Replacing the string iterators, which currently are simple character<br /> 559 pointers, with class objects would greatly increase the safety of the<br /> 560 client interface, and also permit a "debug" mode in which range,<br /> 561 ownership, and validity are rigorously checked. The current use of<br /> 562 raw pointers as string iterators is evil. vector<> iterators need the<br /> 563 same treatment. Note that the current implementation freely mixes<br /> 564 pointers and iterators, and that must be fixed before safer iterators<br /> 565 can be introduced.<br /> 566<br /> 567 Some of the functions in <cstring> are different from the C version.<br /> 568 generally overloaded on const and non-const argument pointers. For<br /> 569 example, in <cstring> strchr is overloaded. The functions isupper<br /> 570 etc. in <cctype> typically implemented as macros in C are functions<br /> 571 in C++, because they are overloaded with others of the same name<br /> 572 defined in <locale>.<br /> 573<br /> 574 Many of the functions required in <cwctype> and <cwchar> cannot be<br /> 575 implemented using underlying C facilities on intended targets because<br /> 576 such facilities only partly exist.<br /> 577<br /> 578 Chapter 22 Locale<br /> 579 ------------------<br /> 580 Headers: <locale><br /> 581 C headers: <clocale><br /> 582<br /> 583 We have a "mostly complete" class locale, with the exception of<br /> 584 code for constructing, and handling the names of, named locales.<br /> 585 The ways that locales are named (particularly when categories<br /> 586 (e.g. LC_TIME, LC_COLLATE) are different) varies among all target<br /> 587 environments. This code must be written in various versions and<br /> 588 chosen by configuration parameters.<br /> 589<br /> 590 Members of many of the facets defined in <locale> are stubs. Generally,<br /> 591 there are two sets of facets: the base class facets (which are supposed<br /> 592 to implement the "C" locale) and the "byname" facets, which are supposed<br /> 593 to read files to determine their behavior. The base ctype<>, collate<>,<br /> 594 and numpunct<> facets are "mostly complete", except that the table of<br /> 595 bitmask values used for "is" operations, and corresponding mask values,<br /> 596 are still defined in libio and just included/linked. (We will need to<br /> 597 implement these tables independently, soon, but should take advantage<br /> 598 of libio where possible.) The num_put<>::put members for integer types<br /> 599 are "mostly complete".<br /> 600<br /> 601 A complete list of what has and has not been implemented may be<br /> 602 found in CHECKLIST. However, note that the current definition of<br /> 603 codecvt<wchar_t,char,mbstate_t> is wrong. It should simply write<br /> 604 out the raw bytes representing the wide characters, rather than<br /> 605 trying to convert each to a corresponding single "char" value.<br /> 606<br /> 607 Some of the facets are more important than others. Specifically,<br /> 608 the members of ctype<>, numpunct<>, num_put<>, and num_get<> facets<br /> 609 are used by other library facilities defined in <string>, <istream>,<br /> 610 and <ostream>, and the codecvt<> facet is used by basic_filebuf<><br /> 611 in <fstream>, so a conforming iostream implementation depends on<br /> 612 these.<br /> 613<br /> 614 The "long long" type eventually must be supported, but code mentioning<br /> 615 it should be wrapped in #if guards to allow pedantic-mode compiling.<br /> 616<br /> 617 Performance of num_put<> and num_get<> depend critically on<br /> 618 caching computed values in ios_base objects, and on extensions<br /> 619 to the interface with streambufs.<br /> 620<br /> 621 Specifically: retrieving a copy of the locale object, extracting<br /> 622 the needed facets, and gathering data from them, for each call to<br /> 623 (e.g.) operator<< would be prohibitively slow. To cache format<br /> 624 data for use by num_put<> and num_get<> we have a _Format_cache<><br /> 625 object stored in the ios_base::pword() array. This is constructed<br /> 626 and initialized lazily, and is organized purely for utility. It<br /> 627 is discarded when a new locale with different facets is imbued.<br /> 628<br /> 629 Using only the public interfaces of the iterator arguments to the<br /> 630 facet functions would limit performance by forbidding "vector-style"<br /> 631 character operations. The streambuf iterator optimizations are<br /> 632 described under chapter 24, but facets can also bypass the streambuf<br /> 633 iterators via explicit specializations and operate directly on the<br /> 634 streambufs, and use extended interfaces to get direct access to the<br /> 635 streambuf internal buffer arrays. These extensions are mentioned<br /> 636 under chapter 27. These optimizations are particularly important<br /> 637 for input parsing.<br /> 638<br /> 639 Unused virtual members of locale facets can be omitted, as mentioned<br /> 640 above, by a smart linker.<br /> 641<br /> 642 Chapter 23 Containers<br /> 643 ----------------------<br /> 644 Headers: <deque> <list> <queue> <stack> <vector> <map> <set> <bitset><br /> 645<br /> 646 All the components in chapter 23 are implemented in the SGI STL.<br /> 647 They are "mostly complete"; they include a large number of<br /> 648 nonconforming extensions which must be wrapped. Some of these<br /> 649 are used internally and must be renamed or duplicated.<br /> 650<br /> 651 The SGI components are optimized for large-memory environments. For<br /> 652 embedded targets, different criteria might be more appropriate. Users<br /> 653 will want to be able to tune this behavior. We should provide<br /> 654 ways for users to compile the library with different memory usage<br /> 655 characteristics.<br /> 656<br /> 657 A lot more work is needed on factoring out common code from different<br /> 658 specializations to reduce code size here and in chapter 25. The<br /> 659 easiest fix for this would be a compiler/ABI improvement that allows<br /> 660 the compiler to recognize when a specialization depends only on the<br /> 661 size (or other gross quality) of a template argument, and allow the<br /> 662 linker to share the code with similar specializations. In its<br /> 663 absence, many of the algorithms and containers can be partial-<br /> 664 specialized, at least for the case of pointers, but this only solves<br /> 665 a small part of the problem. Use of a type_traits-style template<br /> 666 allows a few more optimization opportunities, more if the compiler<br /> 667 can generate the specializations automatically.<br /> 668<br /> 669 As an optimization, containers can specialize on the default allocator<br /> 670 and bypass it, or take advantage of details of its implementation<br /> 671 after it has been improved upon.<br /> 672<br /> 673 Replacing the vector iterators, which currently are simple element<br /> 674 pointers, with class objects would greatly increase the safety of the<br /> 675 client interface, and also permit a "debug" mode in which range,<br /> 676 ownership, and validity are rigorously checked. The current use of<br /> 677 pointers for iterators is evil.<br /> 678<br /> 679 As mentioned for chapter 24, the deque iterator is a good example of<br /> 680 an opportunity to implement a "staged" iterator that would benefit<br /> 681 from specializations of some algorithms.<br /> 682<br /> 683 Chapter 24 Iterators<br /> 684 ---------------------<br /> 685 Headers: <iterator><br /> 686<br /> 687 Standard iterators are "mostly complete", with the exception of<br /> 688 the stream iterators, which are not yet templatized on the<br /> 689 stream type. Also, the base class template iterator<> appears<br /> 690 to be wrong, so everything derived from it must also be wrong,<br /> 691 currently.<br /> 692<br /> 693 The streambuf iterators (currently located in stl/bits/std_iterator.h,<br /> 694 but should be under bits/) can be rewritten to take advantage of<br /> 695 friendship with the streambuf implementation.<br /> 696<br /> 697 Matt Austern has identified opportunities where certain iterator<br /> 698 types, particularly including streambuf iterators and deque<br /> 699 iterators, have a "two-stage" quality, such that an intermediate<br /> 700 limit can be checked much more quickly than the true limit on<br /> 701 range operations. If identified with a member of iterator_traits,<br /> 702 algorithms may be specialized for this case. Of course the<br /> 703 iterators that have this quality can be identified by specializing<br /> 704 a traits class.<br /> 705<br /> 706 Many of the algorithms must be specialized for the streambuf<br /> 707 iterators, to take advantage of block-mode operations, in order<br /> 708 to allow iostream/locale operations' performance not to suffer.<br /> 709 It may be that they could be treated as staged iterators and<br /> 710 take advantage of those optimizations.<br /> 711<br /> 712 Chapter 25 Algorithms<br /> 713 ----------------------<br /> 714 Headers: <algorithm><br /> 715 C headers: <cstdlib> (also in 18, 21, 26))<br /> 716<br /> 717 The algorithms are "mostly complete". As mentioned above, they<br /> 718 are optimized for speed at the expense of code and data size.<br /> 719<br /> 720 Specializations of many of the algorithms for non-STL types would<br /> 721 give performance improvements, but we must use great care not to<br /> 722 interfere with fragile template overloading semantics for the<br /> 723 standard interfaces. Conventionally the standard function template<br /> 724 interface is an inline which delegates to a non-standard function<br /> 725 which is then overloaded (this is already done in many places in<br /> 726 the library). Particularly appealing opportunities for the sake of<br /> 727 iostream performance are for copy and find applied to streambuf<br /> 728 iterators or (as noted elsewhere) for staged iterators, of which<br /> 729 the streambuf iterators are a good example.<br /> 730<br /> 731 The bsearch and qsort functions cannot be overloaded properly as<br /> 732 required by the standard because gcc does not yet allow overloading<br /> 733 on the extern-"C"-ness of a function pointer.<br /> 734<br /> 735 Chapter 26 Numerics<br /> 736 --------------------<br /> 737 Headers: <complex> <valarray> <numeric><br /> 738 C headers: <cmath>, <cstdlib> (also 18, 21, 25)<br /> 739<br /> 740 Numeric components: Gabriel dos Reis's valarray, Drepper's complex,<br /> 741 and the few algorithms from the STL are "mostly done". Of course<br /> 742 optimization opportunities abound for the numerically literate. It<br /> 743 is not clear whether the valarray implementation really conforms<br /> 744 fully, in the assumptions it makes about aliasing (and lack thereof)<br /> 745 in its arguments.<br /> 746<br /> 747 The C div() and ldiv() functions are interesting, because they are the<br /> 748 only case where a C library function returns a class object by value.<br /> 749 Since the C++ type div_t must be different from the underlying C type<br /> 750 (which is in the wrong namespace) the underlying functions div() and<br /> 751 ldiv() cannot be re-used efficiently. Fortunately they are trivial to<br /> 752 re-implement.<br /> 753<br /> 754 Chapter 27 Iostreams<br /> 755 ---------------------<br /> 756 Headers: <iosfwd> <streambuf> <ios> <ostream> <istream> <iostream><br /> 757 <iomanip> <sstream> <fstream><br /> 758 C headers: <cstdio> <cwchar> (also in 21)<br /> 759<br /> 760 Iostream is currently in a very incomplete state. <iosfwd>, <iomanip>,<br /> 761 ios_base, and basic_ios<> are "mostly complete". basic_streambuf<> and<br /> 762 basic_ostream<> are well along, but basic_istream<> has had little work<br /> 763 done. The standard stream objects, <sstream> and <fstream> have been<br /> 764 started; basic_filebuf<> "write" functions have been implemented just<br /> 765 enough to do "hello, world".<br /> 766<br /> 767 Most of the istream and ostream operators << and >> (with the exception<br /> 768 of the op<<(integer) ones) have not been changed to use locale primitives,<br /> 769 sentry objects, or char_traits members.<br /> 770<br /> 771 All these templates should be manually instantiated for char and<br /> 772 wchar_t in a way that links only used members into user programs.<br /> 773<br /> 774 Streambuf is fertile ground for optimization extensions. An extended<br /> 775 interface giving iterator access to its internal buffer would be very<br /> 776 useful for other library components.<br /> 777<br /> 778 Iostream operations (primarily operators << and >>) can take advantage<br /> 779 of the case where user code has not specified a locale, and bypass locale<br /> 780 operations entirely. The current implementation of op<</num_put<>::put,<br /> 781 for the integer types, demonstrates how they can cache encoding details<br /> 782 from the locale on each operation. There is lots more room for<br /> 783 optimization in this area.<br /> 784<br /> 785 The definition of the relationship between the standard streams<br /> 786 cout et al. and stdout et al. requires something like a "stdiobuf".<br /> 787 The SGI solution of using double-indirection to actually use a<br /> 788 stdio FILE object for buffering is unsatisfactory, because it<br /> 789 interferes with peephole loop optimizations.<br /> 790<br /> 791 The <sstream> header work has begun. stringbuf can benefit from<br /> 792 friendship with basic_string<> and basic_string<>::_Rep to use<br /> 793 those objects directly as buffers, and avoid allocating and making<br /> 794 copies.<br /> 795<br /> 796 The basic_filebuf<> template is a complex beast. It is specified to<br /> 797 use the locale facet codecvt<> to translate characters between native<br /> 798 files and the locale character encoding. In general this involves<br /> 799 two buffers, one of "char" representing the file and another of<br /> 800 "char_type", for the stream, with codecvt<> translating. The process<br /> 801 is complicated by the variable-length nature of the translation, and<br /> 802 the need to seek to corresponding places in the two representations.<br /> 803 For the case of basic_filebuf<char>, when no translation is needed,<br /> 804 a single buffer suffices. A specialized filebuf can be used to reduce<br /> 805 code space overhead when no locale has been imbued. Matt Austern's<br /> 806 work at SGI will be useful, perhaps directly as a source of code, or<br /> 807 at least as an example to draw on.<br /> 808<br /> 809 Filebuf, almost uniquely (cf. operator new), depends heavily on<br /> 810 underlying environmental facilities. In current releases iostream<br /> 811 depends fairly heavily on libio constant definitions, but it should<br /> 812 be made independent. It also depends on operating system primitives<br /> 813 for file operations. There is immense room for optimizations using<br /> 814 (e.g.) mmap for reading. The shadow/ directory wraps, besides the<br /> 815 standard C headers, the libio.h and unistd.h headers, for use mainly<br /> 816 by filebuf. These wrappings have not been completed, though there<br /> 817 is scaffolding in place.<br /> 818<br /> 819 The encapsulation of certain C header <cstdio> names presents an<br /> 820 interesting problem. It is possible to define an inline std::fprintf()<br /> 821 implemented in terms of the 'extern "C"' vfprintf(), but there is no<br /> 822 standard vfscanf() to use to implement std::fscanf(). It appears that<br /> 823 vfscanf but be re-implemented in C++ for targets where no vfscanf<br /> 824 extension has been defined. This is interesting in that it seems<br /> 825 to be the only significant case in the C library where this kind of<br /> 826 rewriting is necessary. (Of course Glibc provides the vfscanf()<br /> 827 extension.) (The functions related to exit() must be rewritten<br /> 828 for other reasons.)<br /> 829<br /> 830<br /> 831 Annex D<br /> 832 -------<br /> 833 Headers: <strstream><br /> 834<br /> 835 Annex D defines many non-library features, and many minor<br /> 836 modifications to various headers, and a complete header.<br /> 837 It is "mostly done", except that the libstdc++-2 <strstream><br /> 838 header has not been adopted into the library, or checked to<br /> 839 verify that it matches the draft in those details that were<br /> 840 clarified by the committee. Certainly it must at least be<br /> 841 moved into the std namespace.<br /> 842<br /> 843 We still need to wrap all the deprecated features in #if guards<br /> 844 so that pedantic compile modes can detect their use.<br /> 845<br /> 846 Nonstandard Extensions<br /> 847 ----------------------<br /> 848 Headers: <iostream.h> <strstream.h> <hash> <rbtree><br /> 849 <pthread_alloc> <stdiobuf> (etc.)<br /> 850<br /> 851 User code has come to depend on a variety of nonstandard components<br /> 852 that we must not omit. Much of this code can be adopted from<br /> 853 libstdc++-v2 or from the SGI STL. This particularly includes<br /> 854 <iostream.h>, <strstream.h>, and various SGI extensions such<br /> 855 as <hash_map.h>. Many of these are already placed in the<br /> 856 subdirectories ext/ and backward/. (Note that it is better to<br /> 857 include them via "<backward/hash_map.h>" or "<ext/hash_map>" than<br /> 858 to search the subdirectory itself via a "-I" directive.<br /> 859 </p></div></div><div class="navfooter"><hr /><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="source_code_style.html">Prev</a> </td><td width="20%" align="center"><a accesskey="u" href="appendix_contributing.html">Up</a></td><td width="40%" align="right"> <a accesskey="n" href="appendix_porting.html">Next</a></td></tr><tr><td width="40%" align="left" valign="top">Coding Style </td><td width="20%" align="center"><a accesskey="h" href="../index.html">Home</a></td><td width="40%" align="right" valign="top"> Appendix B. 860 Porting and Maintenance 861 862</td></tr></table></div></body></html>