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