Re: Garbage Collection - The Trash Begins To Pile Up
Kevin Hall wrote:
Le Chaud Lapin wrote:
Kevin Hall wrote:
2. Monarchy<> (what you would call a single-rooted tree)
3. Polyarchy<> (what you wold call a multi-rooted tree)
4. Thread::Object (can't say much, but there *is* a regular model for
multi-threading)
5. Instant, Duration (Boost appropriated good library for doing this)
6. Associative X, where X is any of those in #2 or #3
7. Prioritized X, where X is #6, #2, #3 (not priority queue, Dijkstra's
Algo needs more)
8. Nonce<> (easy to make, very useful to have)
9. String Translator (Spirit of Boost might be related to this)
10. String Parser (Spirity of Boost might be related to this)
11. Various set-based algorithms (AVL, Splay, Binary Regular, Binary
Optimum, Red-Black)
12. Compressors of various sorts (LZ, etc)
13. Ciphers of various sorts (but done cleanly, without too many
assumptions)
14. Synchro primitives (timer, mutex, event, semaphore, etc.)
(2)(3) I'm sorry, I'm not even remotely familiar with either of these
concepts. Could you point me someplace where I could learn more?
(6)(7) Since these depend on (2) and (3), I'm lost here too.
There are no sources. That was my point. There are voids in the set
of primitives offered by STL. And they are not of the esoteric kind,
they are the most basic. STL found list<>, set<>, vector<>, string,
even priority_queue<>. 2 and 3 are "Trees". If you can imagine
representing the chain of command in the military, at the top would be
a commanding general, and at the bottom might be a foot soldier.
That's a tree. This is to be contrasted with another, unrelated type of
tree, various binary and N-ary trees in data structures. By virtue of
B.L. Whorf, I made a point early on to avoid calling my classes "tree"
- that term is so overloaded, there would have been a strong
possibility for the programmer to imagine they were something they were
not. So I spent a few hours trying to come up with something better
than "Single_Rooted_Tree" and "Multi_Rooted_Tree", and decided that I
wanted hierarchies where sometimes there is only one root, and
sometimes their are other root. "Monarchy" immediately came to mind,
and after dismissing the (false) presumption that there is no word in
English that is like "monarchy", but with multiple heads of state, I
chose "Polyarchy".
(4)(14) Threading isn't even part of C++. And it is admittedly very
difficult to figure out how to incorporate threading into a language
with as broad a base as C++. Take semaphores for example. Should C++
use System V semaphores? Posix-style semaphores? Un-named or named
semaphores? Should C++ specify whether semaphores should be process
local or cross-process semaphores? (Linux kernel 2.4 didn't even
support named and cross-process semaphores. Thankfully Linux kernel
does now.) The point is that as soon as C++ defines the types of
synchronization primitives, then C++ cannot be fully implemented on
many OSes. :-(
True. These are the primitives that caused me the most grief to make
them somewhat portable. What I realized was that there is a modeling
problem. The engineers who provide the basis for even thinking about
having portable synchronization primitives need to do more work in
their OS development. As it turns out, Microsoft (actually the old VMS
guard) did very well in this area. No, their API is not portable, but
a C++ programmer can wrap what is given and make it clean. Another
thing I learned, as you hint at, is that not everyone has figured out a
"regular set" and "regular form" for these primitives. Microsoft did,
but it took a while before the Unix people would agree to bona-fide
threads.
(5) What are the 'Instant' and 'Duration' classes? Do you mean a
timestamp object and a time difference class that effectively wraps the
functions in <ctime>?
Yes. But..there are some small changes. Two functions now() and
now(Instant) return and set the system time respectively. The instants
are based on number of seconds past GMT midnight, year 2000. I saw
that another group who gave their library to Boost has already done
this thorougly, so I might switch to their work.
(8) I've never had the need for a Nonce class. A simple google search
showed me there are many different ways to implement a nonce and that a
single template would likely not be sufficient. But I'm naive on the
topic. Maybe there is a universal way a template nonce could be
implemented. But I'm not really sure a Nonce class is really that
fundamental.
Have nonce, randomize it, not such a big deal. Can be make
uncompromisingly portable if one has available a
cryptographically-secure pseudo-random number generator (CSPRNG). This
is a nickel-and-dime class that people involve in secure communications
often need.
(9) What do you mean string translator? Certainly you don't mean an
English-to-Arabic translator class! Do you mean ASCII to UTF-16 class?
I meant translator in "compiler" translator:
1. Lexical Analyzer
2. Parser
3. Translator
The translator takes a string and transforms it to another string. The
rules of translation are supplied as a state argument to the
translator. The grammar for the translation is also supplied. The
goal of this was to make it very easy for novice programmers to do
their own translations in raw C++ (instead calling external system0.
Here is an example that strips the US area code from a phone number
First you define your grammar. My type for this is
AVL::Associative_Set<String__, String__>
three_digits ----> # # #
four_digits ----> # # # #
area_code ----> '(' three_digits ') | three_digits
seven_digits ----> three_digits '-' four_digits
phone_number ----> (area_code | ) (seven_digits)
Then you define the rules for translation, which (simplified for
illustration) amounts to
phone_number ---> seven_digits
Then you define source string..
source: (617) 555-1212
If you define the translation rule correctly, the area code will be
stripped out so you get
555-1212
This has turned out to be very useful for string recognition, parsing,
and translation. The Parser and Translator classes, as it turns out,
use the Associative_Monarchy and Associative_Polyarchy classes.
(11) Set algorithms or set types? If you mean set types, then I'd say
C++ has historically abstained from implementation details -- thus
std::set. If you mean set algorithms, then I'd say that since C++ has
abstained from specifying the types of trees to be used, then it is
difficult to specify the types of algorithms to be used on those types.
Ben Pfaff wrote a nice paper about the relative performance merits of
20 variants of binary search trees (BST's).
http://www.stanford.edu/~blp/papers/libavl.pdf What he found is that
the choice of implementation of a set depends on the anticipated usage
of the set. Red-Black trees are not always the best choice. Sometimes
a regular binary tree will outperform, not just in terms of memory.
Looking at STL, were set is most often implemented as a red-black tree,
this bothered me greatly that I did not have a choice, so when I made
my own containers, I made it so the programmer could choose the
implementation at compile time...BUT!!...it has to be clean, and there
cannot be any hidden consequences. The result is that, instead of
1. Assocative_Set<> (STL map)
I have a family of such:
1. Binary_Regular::Associative_Set<>
2. Binary_Optimum::Associative_Set<>
3. AVL::::Associative_Set<>
4. Red_Black::Associative_Set<>, etc.
This is one reason why I have so many classes. There is a
combinatorial effect. However, because the code is structure to use
the same algorithmic function underneath (something that STL did too),
I did not have to write so much code. And if there is a bug in say, my
AVL algorithm, that bug is everywhere in the entire system, which means
it would have will readily manifest.
(12) A compression framework would be nice, however specific
compression algorithms would be difficult to specify. The only one
that seems that could be reasonably part of the current standard is
ZIP. I think LZ was pattent protected until very recently. 7-ZIP and
RAR are too recent (and RAR is still pattent protected). Anyway, the
problem I see with compression algorithms is very similar to the
problem I see with standardizing GUI libraries: the details change too
quickly. 7-ZIP, RAR, and XP-style GUIs are what are used today. But
tomorrow we'll have new archive formats and Vista graphics. Speaking
of GUI frameworks, I' like to note that C# nor the CLR/CLI define a
graphics framework -- Windows Forms are part of MS's .NET libraries and
not part of the C# language or associated standards. Java is the only
really popular language that I know of that has standardized GUIs and I
don't think that standard Java is going to offer anything to really
take advantage of Vista graphics features (or OS-X graphics features or
DirectX or ...).
Your point about compression algorithms is important. As mentioned,
map<> and set<> do not allow one to choose the type of algorithm. I
would take a different approach. I would expose all of those
algorithms in a toolbox.
(13) A genereal cipher framework would be nice too, but specific
ciphers would likely have similar problems as compression algorithms
and GUI frameworks -- they would be out-of-date by the next standard.
True, so again, I will bring them all out. But, I would not do what
some other crypto writers have done - try to bring all the crypto
primitives under one virtual-function umbrella. I think that sometimes
rigidity itself is what provides flexibility. My crypto primitives are
all rigid, which could be bad, but naming helps. In my current
system, to test, I use
typedef Cipher_RC6::Cipher<32,20,16> Symmetric_Cipher;
typedef Cipher_RC6::Key<16> Symmetric_Key;
using namespace Cipher_RSA;
using namespace Hasher_MD5;
These crypto primitives are used throughout my system in many places.
But MD5, we all know, is no longer robust for true cryptographic
strength, and RC6 is proprietary. That's not a problem. As soon as I
finish testing, I am going to change RC6 to Rijndael and MD5 to
SHA_256, hit the recompile button, and be done. Everything will work
as expected because the naming is consistent.
Le Chaud Lapin wrote:
There is also the issue of libraries. STL is deficient. I could name
10-12 classes that are *absolutely fundamental* in systems engineering
I'm pretty sure I would qualify as a systems engineer and even if I
didn't, I'm pretty sure my company would qualify as a "systems
engineering shop" (see next paragraph for what I believe are
qualifications). Anyway, the only feature you mention that is
*absolutely fundamental* to the work we do relates to threading. And
here we have tried our best to provide an abstraction layer for things
like semaphores, timers, and events -- but we have come across problems
with differnt OSes where things could not be implemented fully -- Linux
kernel 2.4 being the worst example. I don't see how C++ can require
compiler vendors to provide much more than atomic operations -- and
even here, not all processors where C++ is currently supported support
atomic operations. But the good news is that the ISO C++ comittee is
actively researching what can be specified for threading.
So both should be done in parallel. The OS people need to do their
part. The C++ people need to do their part. But from what I have seen,
the burden is more on the OS, not C++. It is generally agreed that a
stack is a welcome primitive in a system. People are not so sure about
the whole threading, synchronization stuff. They need to figure this
out first, I think, before assuming that the language will help.
Again, based on my own experiences, Microsoft (gulp). leads in this
area. No, the API is not super pretty, but the pieces are all there.
(I work for a motion control company that creates our own hardware,
uses FPGAs and creates our own FPGA images, creates our own embedded
software (for DSP chips, PPC processors), our own libraries for our
customers to use (for various real-time and non-real-time OSes), and
our own Windows utilities, with some even written in .NET. Safety is
absolutely critical since we deal with many medical applications. And
we very frequently work side-by-side with our customers to help ensure
the soundness of the entire machine from the software all the way down
to the mechanical and electrical systems. As far as I know, this
qualifies as "systems engineering". And I have worked with all of
these areas with the exception of the hardware and FPGA design --
though I've had to be intimately familliar with certain aspects of
both.)
Sure, this is systems engineering.
I often think that all of this talk about ways of designing systems
would be settled if young engineers were forced to do all that you
wrote above, but alone. Success would not be the goal. [Kalman filters
will give even the most determined engineer gray hair. :)] . But it
would force them to think about the entire system, about how hard it is
to design something on piece of software that might or might not throw
an exception for no reason, that is so flexible that you cannot use it
as part of your foundation; or how, if you have 12,000 components, all
operating at once, you can sleep a lot better at night knowing that
each component is going to do its job, cleaning up after itself, and
presenting a contract to the other adjacent little components, that it
honors, and expects those components to honor, and all will work
together.
This is not what happens in software today. Today
it's..."well....hmmm...exception huh? not reproducible??.....well...I
guess we could wrap the whole thing in a catch block...delete the
corrupt file, unload the DLL, and reload it. We have to ship the
product."
-Le Chaud Lapin-
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]