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