on Fri Nov 09 2007, Yossi Kreinin <yossi.kreinin-AT-gmail.com> wrote:
> On Nov 6, 9:39 pm, David Abrahams <d...@boost-consulting.com>
>> > This seems to imply that the sequence size is bound by a constant,
>> Yes. But that's okay; you can change the constant.
> Well, I can also change any other fixed size limit like a buffer size > constant, but I'd rather have it dynamically allocated as required by > the context where it's used...
> And I still don't see how you can set that constant to an arbitrary > value. You can only generate templates with arbitrary number of > parameters using macros, and macros don't really support compile time > loops, so the maximal number of iterations in macro meta-programming > is /also/ limited by a constant,
Boost.Preprocessor (which is more portable to broken preprocessors --- of which there are surprisingly many) does rely on fixed limits, but those limits are so large in practice that you'll never run into them.
> and *this* constant *can't* be a preprocessor parameter since C > macros can't generate C macros.
> So isn't the compile time constant bound by another compile time > constant?
> I was thinking about nesting these templates, so you'd get a tree, > which doesn't have the fixed size limit problem, but has a > complexity problem, which is probably much worse in practice.
Tree structures are good for limiting recursion depth, which can be costly in compile time.
>> Sure you can. Anything you can do in other pure functional >> languages, you can do with templates. It's just a lot uglier ;-)
> I rest my case :)
You won't ever hear me arguing that TMP is the most elegant approach possible. However, your case was, in this instance,
> I think that implementing type lists to be "compile time type hashes > or sets" (that is, represent hash tables using TMP) is really really > hard (both for a human to write or read and for a compiler to > process).
and my point was that once you have the library written that does these things, it gets pretty easy to read the code that uses them.
> In practice, I think that TMP proponents will claim that compile time > is cheap,
I would never claim that. It's a real concern, which is why in my book with Aleksey Gurtovoy we do extensive efficiency analysis.
> not that TMP is easy to implement efficiently in terms of compiler > resources
> Boost.Preprocessor (which is more portable to broken preprocessors --- > of which there are surprisingly many) does rely on fixed limits, but > those limits are so large in practice that you'll never run into them.
I referred to the limits of Boost.Preprocessor, on which AFAIK the code we were talking about is based.
In an adjacent sub-thread, you told how people would complain about functions with 15 parameters which weren't at the time supported by some of the library interfaces. 15 is a whole lot of function arguments, but of course a function with 100 arguments is less likely - that is, in "application code". Well, the broken preprocessors you mention break on macros which are extremely unlikely to appear in "application code", and yet the problem does get in the way of people working on libraries based on meta-programming. So problems you run into in practice depend on what you practice :) And I think that if you practice meta-programming, especially in C++, you're stretching the limits of the infrastructure, including fixed-size limits.
I think this discussion has reached the point where little new can be added, and evaluating the importance of the arguments can only be done subjectively; I don't think that the point above strictly "proves" anything.
> > So isn't the compile time constant bound by another compile time > > constant?
> I don't follow you.
I referred to the "compile time constant" that is the recursion depth limit of Boost.Preprocessor and how it limits compile time constants such as BOOST_MPL_LIMIT_VECTOR_SIZE. In case I still didn't clarify myself, let me just say that we've already discussed this point anyway...
> my point was that once you have the library written that does > these things, it gets pretty easy to read the code that uses them.
I see several problems with this:
* Library implementations are rarely completely hidden - the user is exposed to them to varying degrees when dealing with compile time and run time errors. This is especially true in C++ (I know that C++0x is supposed to simplify compile time error handling, I'm talking about what we have now).
* We're discussing a set of programming techniques, not just a library; I claim that using these techniques for new code is a high cost to pay for the functionality gained, because of the complicated ways to achieve simple things. And if all we needed was the functionality in a closed set of libraries (as opposed to an open set of things which can be implemented with TMP), I'd rather have that functionality built into the compiler since that would hide the complexity much better. Of course one can say that deploying that solution is much harder. Both the ability to hide the complexity without "adding to the compiler" and the ability to "add to the compiler" depend a lot on the details of a programming language, so this would be a whole new discussion.
* One of the consequences of the complexity is either reduced portability, or extensive testing with many compilers and a non- trivial investment in workarounds for particular compilers, or both.
Again, I think the importance of all these points (or respective counter-arguments) can only be evaluated subjectively, with attitudes ranging from "you simply shouldn't care about the inner workings of a library" to "it's simply unreasonable that you go through such complications to implement something as simple as a loop in compile time", through many the less "simple" judgments.
> > In practice, I think that TMP proponents will claim that compile time > > is cheap,
> I would never claim that. It's a real concern, which is why in my > book with Aleksey Gurtovoy we do extensive efficiency analysis.
Well, I wasn't talking about people with lots of TMP and/or library design experience, but rather about casual TMP users applying it to solve specific problems. And as I said, this is a "social" rather than "technical" thing, so when I mention it, it can clarify my point but can hardly make a valid argument by itself. The more technical argument in this context is that optimizing TMP is much harder than, say, optimizing low-level number crunching code, because both the performance measurement and the mapping between the code and the complexity of its processing by the compiler are pretty complicated in this environment.
In all this, I'm not saying that "hard" is "bad", just that the result has to be worth the trouble.
On Nov 2, 8:32 am, "Nevin :-] Liber" <ne...@eviloverlord.com> wrote:
> For instance, you claim that people don't measure performance of > templated code <http://yosefk.com/c++fqa/templates.html#fqa-35.10> and > then go on to claim that templated code in most cases is slower than non > templated code due to i-cache effects. Yet nowhere can I find any of > *your measurements* which show this to be true. Where are your > measurements?
I don't claim that (all) people don't measure performance of templated code, and I don't claim anything about templated code being slow in "most cases"; nobody can back up this claim, nor can anybody prove the opposite.
Regarding measurements - here's a numeric data point: with Green Hills C++ for ARM, I saw iostream compiled to >2M of bytecode in a 10M executable (code was replicated about 100 times since that's the number of translation units that #included iostream). This means that most of the time, calls to iostream functions resulted in instruction cache misses.
Can you reproduce it? I can't send you the code, so it isn't necessarily trivial (you can trying buying a license for Green Hills C+ + for ARM and generating 100 files #including iostream, but I'm not sure it will reproduce with files not actually using it, and I don't know which usage patterns are the main trigger).
With most of these things, we can establish the existence of something, but rarely quantify things. You can say that templates generate fast code and name valid reasons, I can point out valid reasons for the opposite, but it's impossible to quantify the relative importance of these things since we can't formally represent the "distribution" of programs, systems, compilers and workloads.
So everyone has to ultimately make a subjective judgment based on one's personal experience and some informal mental representation of these "distributions". For the purpose of making such judgment, the only useful information to emerge from this kind of discussion is a list of what can happen, but not how often it happens or how important its consequences are.
> Now, pick any other language, and show us that this C++ version (with > optimizations turned on, of course, since inlining is an important part > of templated code performance) is slower for most invocations of this > with fundamental types (this way we leave out variations due to poorly > written operator<) and various sizes and initial randomness of the > array. Other than handcoded assembly by an expert, I seriously doubt > you will.
Well, the two problems mentioned by the FQA - the generation of multiple functions identical at the assembly level and the use of "helper types" which force you to stuff things into structures which then aren't optimized out - don't apply to the sort example, so it doesn't make a counter argument. BTW, you didn't mention the point about types; compare the code generated from std::for_each with a Boost.Lambda functor to code generated from an equivalent plain vanilla for loop.
IMO the interesting thing about std::sort is not about how it is slower than the alternatives (AFAIK it isn't and I never claimed it was), but how it isn't faster than, say, qsort, if your compiler does good link-time inlining. The interesting thing about this is that with modern compilers, you can have separate compilation *and* optimization at the point of call, but C++ chose to put the burden on the front-end and the users waiting for it to recompile the code of std::sort over and over again. Actually, an optimizing back-end isn't harder to get right than a C++ front-end.
As to non-portable optimization - you don't have to be an "expert" to vastly outperform portable C or C++ code in areas such as number crunching. Sorting and especially non-flat data structures are the classical example illustrating the speed of portable code, since little can be done using target-specific instruction set extensions to speed up this kind of thing. However, C or C++ with intrinsics (one of today's most popular assemblers) beat portable C or C++ elsewhere very convincingly.
> You make other wild claims, such as vector<int> and vector<void*> not > sharing code, yet I know of a least one C++ implementation (Metrowerks) > that has done so for years.
Well, I know of some implementation that haven't been doing this for years. I never claimed no implementation did this. What I claim is that if you care about performance and portability to several targets, then the fact that many implementations don't do this is a problem. And if you don't care about portability and performance, one of the biggest concerns is most likely safety, so using C or C++ doesn't sound like a good choice anyway.
On Nov 7, 12:02 pm, "Alf P. Steinbach" <al...@start.no> wrote:
> > But then paging doesn't really solve this problem. It's enough to have > > a single byte occupied inside a page to make it impossible to dispose > > it; with fragmentation, you end up exactly with this problem - little > > objects scattered across the memory.
> With a single byte allocated that logical address can just be mapped to > some other page.
I don't know if we're sliding into off-topic land, but I don't understand this. You have a byte mapped at the virtual address 0x80000007, and 16K pages. How are you going to avoid allocating a 16K chunk of physical memory to keep the byte? If you stuff the byte into some other physical page, already keeping bytes corresponding to some other virtual chunk (say, at the virtual address 0x84500000), the byte may be overwritten (when someone writes to the address 0x84500007). I mean, the page size defines the granularity of the virtual memory management, so how can you optimize the handling of smaller chunks?
What you can do is make pages smaller (and the page table larger, so at some point it defeats the purpose).
> > But even if you have paging and entire free pages, I don't think most > > real OSes will actually reclaim the page. malloc typically runs on top > > of something like sbrk(), which manages a stack - you can yank more > > pages or reclaim pages at the end of the data segment, but you can't > > free the pages in the middle of the data segment. At best, the pages > > at the middle will be eventually swapped out, littering the disk > > instead of the RAM (and some systems with virtual memory are > > diskless).
> This is an OS problem, not a language or C++ or GC problem.
Well, it is a practical problem with languages defined to allow unmanaged implementations incapable of doing heap compaction. That's because in these languages, a managed implementation becomes impractical as the language matures since it won't work with a large body of unmanaged compiled legacy code. And you can't change the major operating systems which can't reclaim pages in the middle of the dynamic data segment. So it's really *your* (the user's) problem, not an OS or a language or C++ or GC problem :)
Theoretically you are right, in the sense that an OS could do this differently.
> > If a language is built such that the run time knows where > > all the pointers are and can update them upon heap compaction, the > > problem is solved; so I do think it's a "linguistic" issue, not a > > "systems" issue.
> Most probably incurring the Long Inconvenient Pause (LIP (TM))...
Well, I didn't study this very deeply, but I think that you can do incremental heap compaction. I'm quite positively sure that real time applications (definitely soft real time ones) can work that way, by allocating a certain time slot for periodic incremental heap compaction.
> > Overall, I think this justifies special treatment of memory.
> Yes.
As I've already said in an adjacent thread - I rest my case :)
In article <955c8150-52dc-48e8-aa6d-43ea050b3da8@ 41g2000hsh.googlegroups.com>, vattilah-gro...@yahoo.co.uk says...
[ ... ]
> As I pointed out your criteria misses an essential point.
No, it does not.
> If you bring > the table into run-time you also bring all its dependants into run- > time. That may have severe performance impacts. Consider:
> constexpr int foo (constexpr int i); > constexpr int result = foo (table.lookup (42));
You're the one missing the point here. It looks more and more like you haven't even glanced at the paper Andrei cited, so let's review.
As the paper made quite clear, this code is dealing with voice input -- specifically, the input is something like a number of people conversing, and this is involved with identifying the person who's speaking at any given time. The input that's used to look things up in the table is NOT a static part of the program, and normally won't even exist when the program is written.
> The function foo may be arbitrary complex. If the lookup is a > constexpr then result can be evaluated at compile-time. Otherwise it > has to be evaluated at run-time. Now put that expression into a > crucial innerloop of the run-time program, and you may see significant > effects on performance.
No, the function foo may NOT be arbitrarily complex -- as the paper made _completely_ clear to anybody who bothered to read it at all, it's a natural logarithm. Far from being arbitrarily complex, it's so simple that it's faster to compute it that to read it from main memory. The table is ONLY effective if it's kept small enough to fit into cache.
What we're left with is simple: in other situations that are almost completely different, being able to use the results of computations as constants can be useful -- and I've even cited some of those situations. In THIS situation, however, the absolute best we can hope for is that computing the table at compile time would be a rather minor optimization in the time taken to initialize the program. All the evidence in the paper suggests that precisely the opposite would be the case though -- specifically, if it's faster to compute the data than retrieve it from main memory, then it's almost certainly faster to compute the data than retrieve it from mass storage.
All the hypotheticals about results based on static input and arbirarily complex functions won't change the fact that in this case, the input is dynamic and the function is faster to compute than to retrieve from mass storage or even main memory.
In article <ApmdnfIju6SC3KbanZ2dnUVZ_qHin...@comcast.com>, wal...@digitalmars-nospamm.com says...
[ ... ]
> > In fact, I'm pretty sure it's compiled and worked the first time, with > > every C compiler I've ever tried, without my having to define a single > > macro or edit a single line of code.
> Having a tool compile successfully on another platform is not at all > the same as it being debugged and tested on that platform.
Yes, but note where I said "and worked". It comes with test grammars and the correct results for those grammars, so regression testing is quite trivial (and, as I said, I've yet to have it fail).
> And yes, I've downloaded source code to tools and tried to compile > them on various platforms. Often, the build instructions leave much to > the imagination. Then, when you try and build it, various messages pop > out, and maybe it doesn't build. It's not always obvious how to fix > it. I had this problem recently with putty. I eventually solved it by > finding already ported/debugged/tested binaries and downloading those.
Once again, you note an unrelated example. The fact that some tools are non-portable does not imply that all tools are non-portable. Yes, if you carefully choose tools that aren't portable, you can find them. That hardly means that none of them is portable, or that your own code is three times as likely to be portable as somebody else's.
> David Abrahams wrote: > > on Wed Nov 07 2007, "Andrei Alexandrescu (See Website For Email)" > > <SeeWebsiteForEmail-AT-erdani.org> wrote:
> >> David Abrahams wrote: > >>> on Mon Nov 05 2007, Walter Bright <walter-AT-digitalmars-nospamm.com> wrote:
> >>>> Allow me to quote from the first paragraph of "Specifying C++ Concepts" > >>>> by Reis and Stroustrup:
> >>>> "Current work on improving templates > >>>> focuses on the notion of concepts (a type system for > >>>> templates), which promises significantly improved error diagnostics > >>>> and increased expressive power such as concept-based > >>>> overloading and function template partial specialization." > >>>> -- http://www.research.att.com/~bs/popl06.pdf
> >>>> It's the FIRST thing mentioned about what concepts are intended for. > >>> Apparently I need to clear this up. Improved diagnostics is the first > >>> thing mentioned about the effect of supporting concepts, not what > >>> they're *for*.
> >>> The exceptions feature promises cleaner code, but it's not *for* > >>> cleaning up your code; it's for error handling. When they were > >>> invented, cars promised less time spent traveling, but they weren't > >>> *for* reducing the amount of time you spend on the road, they were for > >>> getting from point A to point B. > >> I think this is getting into semantic hair splitting. I agree with > >> Walter that philosophical arguments about the meaning of "for" aside, it > >> is reasonable to infer from the citations produced that the perceived > >> main benefit of concepts is improved diagnostics in templated code.
> > Maybe so, but it's still the wrong inference.
> >> If that's the case,
> > It's not.
> I don't have much to work with, then. When I asked the point blank > question "what are concepts for"? I got:
> "They're an element of comprehensive support for GP in C++".
> And I'm an intricate combination of molecules. Doesn't shed much light...
Actually, there're many implications of Concepts:
#1, Better Error-Message (obviously) #2, Early Type-Checking (resolving the dependent&non-dependent name hair-splitting) #3, Facilitate better IDE auto-complete (When 't' is of type T, compiler won't know how to list its members when you type "t.", but when 't' is of type "Concept RandomIter", things're different) #4, Concepts as "Documents-in-Code". (If assertions are important, so is this) #5, Facilitate better Refactoring tool. (see http://beust.com/weblog/archives/000414.html) #6, Syntax is the hindrance of semantic re-use. But concept_map makes non-intrusive adapter-layer piece of cake. #7, Make obsolete many unwieldy template tricks/workarounds (e.g. SFINAE, tag-dispatching) by supporting a first-class mechanism for intuitive overloading. #8, Eliminate the danger of treating syntactic-conformance as semantic- conformance.
On Nov 11, 12:36 am, Yossi Kreinin <yossi.krei...@gmail.com> wrote:
> On Nov 7, 12:38 am,AlexShulgin<alex.shul...@gmail.com> wrote:
> > Sorry, I haven't stated my point clear enough: there are cases where > > designing an interface is harder (or is of comparable complexity) than > > providing implementation, and from my experience they are the most > > common cases. Of course, there are simple cases where it is not true > > and your FQA shows some of them.
> The FQA mentions examples like face recognition and file systems > implementing an existing (and typically quite small and clear) system > call API. These cases are not at all "simple" in terms of > implementation.
Sorry, you've missed the point again (or I wasn't clear enough even more (-: ). By "simple cases" I meant easy-to-show cases there interface is easier to do than implementation, not "simple in terms of implementation". Yep, I agree there are such easy-to-show cases, however your examples with compiler etc., are not particularly good at demonstrating it, IMHO.
> > As to real world example: suppose you need to design an abstract class > > (or class hierarchy) to provide a file system API. I'd expect > > concrete methods to be easier to implement since they would be most > > probably unrelated to each other (or related only weakly), whereas the > > interface(s) are sort of a bigger picture issue--you have to think > > thoroughly how things interact and influence each other in order to > > design it properly. Add the need to support various different real > > world file systems (FAT, ext2, NTFS, etc.) plus yet-to-be-known > > systems and the high costs of later changes and you'll see the result.
> You're talking about wrapper code: a class library working on top of > existing file systems and providing a uniform interface to them. It's > not an easy task, but arguably /implementing/ a file system (ext2, > NTFS, etc.) well at the system level is much harder.
OK, but provided the implementation of filesystems already exists in the OS, it still not an easy task to design that wrapper classes don't you think?
> The FQA refers > to /this/ example when it talks about the interface of > write(fd,base,size) being much simpler than the implementation.
> I think that lots and lots of cases where the interface is the hard > part are in fact cases of "middle management" code, which propagates > calls and computes nothing (sometimes people really need such code, > frequently they don't though and only do it for syntactic sugar). Of > course there are other cases where the interface is hard as well, I > just think that the opposite case is frequently overlooked by people > with aptitude in "programming linguistics".
Agreed, it's especially easy to overlook them, IMHO, if you don't talk about the problem at hand in terms of interface/implementation. ;-)
[snip]
> > Point taken, but it's likely to be more closely related to the quality > > of implementation: for example, VS2005 'knows' about standard > > containers and show their contents in the debugger in a readable way, > > and VS2003 doesn't.
> What happens when a container is partially overwritten in VS2005 > though?
Good point. And what happens if your custom container implementation in C is partially overwritten? See, it's not easy to tell whether you suggest using higher level (interpreted) language or "lower" level C instead of C++ here...
> What about when you use STLPort instead of its implementation > (which of course violates the standard since the standard library is > "built into the language"; those STLPort people should be prosecuted)?
I don't quite follow you: what do you mean by "violates the standard"?
> > Point taken, however, with the source code at hand it transforms into > > portability issue (see below). And no one forces you to use > > proprietary third-party libraries, hopefully... :-)
> Let me point out that C++ seems to be the only language where library > *interface and design* (not just implementation details) depend on > front-end features tricky enough to be implemented differently by > different compilers, to the extent making it impossible to use the > library on some systems. See the Blitz++ home page, for example.
> This isn't really about the ABI-related portability, it's about syntax- > related portability.
It would make sense several years ago: as others have noted, blitz++ home page lists outdated compiler versions. And it explicitly states "Not all compilers _implement enough_ of the ISO/ANSI C++ _standard_ to compile Blitz++" (emphasis mine).
> > > Sometimes this is "not a problem", except you have to deliver your own > > > libraries compiled and tested with 3 compilers, each with its own > > > front-end (grammar) and back-end (codegen) bugs.
> > So this is more of a portability issue than the real need to link > > against code produced with another compiler.
> In these cases, yes. But sometimes you do need to use closed-source > libraries. C++ is supposed to support it; show me one place where > anybody who worked on the development of C++ claims that it is a non- > goal. Well, it is "supported", but not very well.
And the real problem is caused mostly by compilers marketing, not language itself, I suppose... ;)
> > This way you do not need `const*' _and_ have less error-prone code. > > Please note, that in your code the caller must ensure that:
> > 1. Lifetime of `comments' vector does not exceed the `lamers' one. > > 2. Lifetime of every element of `comments' vector does not exceed the > > lifetime of a corresponding `lamer' object for which the LameComments > > were obtained.
> /Of course/ it's more error prone because of lifetime issues! It > wouldn't be in reference-based languages with garbage collection. In C+ > +, I'm really supposed to have a smart pointer class and hope that > lamers don't have cyclic references in their comments (pretty > unlikely, that). This is another can of worms, and copying is a good > way out of this one, two, except for the performance penalty. I think > that your solution (copying) is in many cases /better/ than the smart > pointer solution; people in adjacent threads will disagree.
Will they? I would really like to hear... ;-)
> > What if at some point you decide to change the container type from > > `vector' to `list'? What if you need to work with both types of > > containers? See, here you store Lamers in vector, and there--in > > list. Would you end up copying elements from list to vector and then > > calling the function?
> 1. I normally /don't/ make these decisions ("change vector to list"), > and over the years I stopped caring about this argument. If the data > structure affects performance, changing it is a royal pain since the > performance of all code touching it will be changed and you'll have to > do lots of rewriting to fix the parts that are now slow; touching all > places where you used random access instead of iterators is the easy > part (and if you typedefed the container and used iterators, many > things will only have to be recompiled). And if the data structure > doesn't affect performance, why change it?
Agreed, I don't remember myself ever making such a decision, but this argument still constantly shows up in my mind, dunno why. :-)
> 2. Sure, when one place expects a list of Lamers and another one > expects a vector of them, templates are a way out of the problem. But > I wish there was a standard way to use virtual functions to iterate > over different containers instead, so that I could compile the > function code separately from the calling code. It isn't hard to write > something like this on top of STL, but it's non-standard, which in > this case matters since you lose opportunity for binary > interoperability between functions traversing containers and the > calling code, and it's sort of frowned upon in the C++ community since > you're supposed to use templates here (but I can live with the > latter :) )
Yep, and using virtual functions to iterate containers certainly have performance penalty over use of templates.
> > > Do you know how much time the previous real example took me to invent?
> > So probably this is a sign of how much that example is far from the > > real-world? ;-)
> C'mon :) It's a trivial filter, of the kind implemented by the Python > generator expression
> (x.m for x in seq if pred(x.m))
> It should be /completely trivial/ to implement, since it's the bread > and butter of programming.
And it's indeed _trivial_ to implement, if you didn't make the promise not to use C++ templates ever.
Now, I don't think further discussion will get us somewhere. My bottom line is: I agree with most of the facts you have presented, but not with your conclusions.
See, every programming language has domain (e.g. no one would expect, I think, time critical image processing to be done in very high-level interpreted language and quick one-shot programs be done in C or C+ +). And every language have it's specifics (you may call them "issues"), but being aware of them in the first place allows you for proper choice of language per task.
Your FQA might convince someone with no or little C++ experience that "nothing should be done C++", but I don't think you'll convince anyone out there in this newsgroup. ;-)
Again, I agree with most of the facts, but do not see most of them (or a combination of them) as "problems", but rather "known issues" or even "language features". Facing one of them late in the production cycle _is_ certainly a problem if you weren't aware of it in the first
On Nov 18, 12:46 pm, Jerry Coffin <jcof...@taeus.com> wrote:
> You're the one missing the point here. It looks more and more like you > haven't even glanced at the paper Andrei cited, so let's review.
Guilty as charged. I may have unfairly mistaken your post as trying to make a more general statement. Your criteria for selecting between compile-time and run-time may very well make sense for the motivating program in this paper (the ICSI Speaker Diarization Engine).
> As the paper made quite clear, this code is dealing with voice input -- > specifically, the input is something like a number of people conversing, > and this is involved with identifying the person who's speaking at any > given time. The input that's used to look things up in the table is NOT > a static part of the program, and normally won't even exist when the > program is written.
Now that I've glanced at the paper I'll just point out to the casual reader of this thread who wont bother reading the paper that it has a very narrow focus: the fast computation of the logarithm function (ICSILog), using table lookup and exploiting cache properties on modern CPUs. Speech processing is only the motivating application and you'll find little about that, and nothing at all about the topic of this thread; computing at compile-time vs run-time.
So allow me to shift the discussion to the broader issue that peaked my interest to such degree that I actually bothered to post: What criteria makes sense for deciding to compute something at compile-time vs run-time.
Criteria: If the load time of the result takes longer than the computation of the result at run-time (which includes the load time and execution of the code to compute it), it makes no sense to compute it at compile-time.
This makes sense for a single computation in isolation. But it doesn't scale. It may not be true if the computation is part of a larger program because of the cascading effect I mentioned: If you bring a computation into run-time you also bring all its dependants into run- time as well.
> No, the function foo may NOT be arbitrarily complex -- as the paper made > _completely_ clear to anybody who bothered to read it at all, it's a > natural logarithm. Far from being arbitrarily complex, it's so simple > that it's faster to compute it that to read it from main memory.
You've misunderstood. In my example, foo was not a stand-in for the logarithm function. It was an illustration of an arbitrary complex dependant of some expression that may or may not be computable at compile-time. Let me make it clearer (assuming language support):
on Sun Nov 18 2007, Mathias Gaunard <loufoque-AT-gmail.com> wrote:
> On Nov 15, 4:11 pm, David Abrahams <d...@boost-consulting.com> wrote: >> As we introduce modules, >> variadic templates, and modular metaprogramming, I hope we'll be able >> to put most uses of the preprocessor behind us.
On Nov 19, 2:08 pm, Alex Shulgin <alex.shul...@gmail.com> wrote:
> > What happens when a container is partially overwritten in VS2005 > > though?
> Good point. And what happens if your custom container implementation > in C is partially overwritten? See, it's not easy to tell whether you > suggest using higher level (interpreted) language or "lower" level C > instead of C++ here...
For starters, we don't even know what "here" is (the domain), all we know is that there's a container, so I can't suggest a language. However, this is irrelevant. It's enough to point out that in C, picking up the pieces of the data structure manually is easier since it's less hostile to symbolic debugging (reading type names generated from templates and typing them to have the debugger cast a pointer, if it can parse the type name at all, is one example). And when you can afford safer (and costlier) languages, the overwriting wouldn't happen in the first place.
> > What about when you use STLPort instead of its implementation > > (which of course violates the standard since the standard library is > > "built into the language"; those STLPort people should be prosecuted)?
> I don't quite follow you: what do you mean by "violates the standard"?
According to the C++ standard, the standard library is "built into" the implementation; you shouldn't assume that you can, say, replace the header files shipped by the vendor with something else defining std::vector, etc. and hope that anything will work.
It's not the most important point in the original context; note, however, that the fact that the standard is defined this way effectively means that you lose the practical advantages of having stuff like std::map implemented "as a library" instead of having it implemented by the compiler (in fact the standard says it /is/ implemented by the compiler). You are left with the drawbacks (cryptic error messages, interoperability with pre-standard map classes, recompilation of the container code many times over, etc.)
> It would make sense several years ago: as others have noted, blitz++ > home page lists outdated compiler versions. And it explicitly states > "Not all compilers _implement enough_ of the ISO/ANSI C++ _standard_ > to compile Blitz++" (emphasis mine).
What I care about is the de-facto status. Porting from gcc 3 to gcc 4 raises lots of problems of syntactic compatibility, for example; both came out years after the C++ standard. All versions of VS, gcc and Green Hills C++ I've used /crashed/ on quite simple C++ code.
Yes, Blitz++ supports gcc starting from 2.95. Do you think it just so happened, or is it more likely that it took a certain amount of effort? Note that Blitz++ compiler support page doesn't list a single tool chain for an embedded target (except for gcc cross-compilers, unless I missed something). If I want portability to major desktop targets, many languages provide it; C gives much more portability, and C++ in fact gives less (because of the above-mentioned effort; from my experience, this effort of maintaining the compatibility of non- trivial C++ code with several implementations is very significant).
Theoretically, C++ has a standard, so these are non-problems. What I care about though is what actually happens. And I learned, the hard way, that if I want to spend time on functionality and not fighting with the front-ends of the many targets, staying away from the non- trivial bits of C++ syntax is the way to go. Of course nobody has to believe me or anybody else claiming the same; from my experience, it's much, much more interesting to assume that "C++ has a standard" and check things out for yourself.
> > In these cases, yes. But sometimes you do need to use closed-source > > libraries. C++ is supposed to support it; show me one place where > > anybody who worked on the development of C++ claims that it is a non- > > goal. Well, it is "supported", but not very well.
> And the real problem is caused mostly by compilers marketing, not > language itself, I suppose... ;)
Well, this doesn't happen with many other languages; it has to do with the language itself. But I don't really care about who or what should be blamed, just what should be done in practice.
> > I think > > that your solution (copying) is in many cases /better/ than the smart > > pointer solution; people in adjacent threads will disagree.
> Will they? I would really like to hear... ;-)
Check out the adjacent threads.
> Yep, and using virtual functions to iterate containers certainly have > performance penalty over use of templates.
If you do something non-trivial with the elements, it doesn't matter; I was talking about these cases.
> > It should be /completely trivial/ to implement, since it's the bread > > and butter of programming.
> And it's indeed _trivial_ to implement, if you didn't make the promise > not to use C++ templates ever.
I didn't make that promise and I use them (BTW, the FQA includes several explicit advices to /not/ ban C++ features). However, IMO, having to separate the code of a trivial filter into a template function and passing all context which the code may need as parameters is not trivial. Having the code of an entire project templated to avoid problems with const correctness is also non-trivial, in terms of compile time, for example.
On Nov 19, 1:08 pm, Alex Shulgin <alex.shul...@gmail.com> wrote:
> See, every programming language has domain (e.g. no one would expect, > I think, time critical image processing to be done in very high-level > interpreted language and quick one-shot programs be done in C or C+ > +). And every language have it's specifics (you may call them > "issues"), but being aware of them in the first place allows you for > proper choice of language per task.
The main reason image processing is slow in those high-level languages is because often you can't have arrays of objects, only arrays of pointers to objects. Being able to store the objects themselves and not pointers to them is required to write efficient code. And to do that, you need to specify how an object is to be copied, moved etc. Which makes C++ the only high-level language capable of being efficient.
The explanation isn't very clear. If it's just about adding compile-time reflection, it should be quite straightforward to expose information with Boost.MPL.
> On Nov 19, 1:08 pm, Alex Shulgin <alex.shul...@gmail.com> wrote:
> > See, every programming language has domain (e.g. no one would expect, > > I think, time critical image processing to be done in very high-level > > interpreted language and quick one-shot programs be done in C or C+ > > +). And every language have it's specifics (you may call them > > "issues"), but being aware of them in the first place allows you for > > proper choice of language per task.
> The main reason image processing is slow in those high-level languages > is because often you can't have arrays of objects, only arrays of > pointers to objects. > Being able to store the objects themselves and not pointers to them is > required to write efficient code. And to do that, you need to specify > how an object is to be copied, moved etc. > Which makes C++ the only high-level language capable of being > efficient.
I don't think so. The main reason is that the algorithm is generalized thus suffering from abstraction penalty. For example, BitBlt from win32 could transfer a pixel block from a source to a destination after a possible transformation by a brush, this makes the implementation of BitBlt have to be generalized so that it can cope with any sort of source/dest/brush combination, which, in turn, will make the code look like this:
for (y = 0; y < cy; y++) for (x = 0; x < cx; x++) { switch(rop) { case 0x00: D[y][x] = 0x00; break; ... case 0x60: D[y][x] = (D[y][x] ^ S[y][x]) & P[y][x]; break; ... case 0xFF: D[y][x] = 0xFF; break; } }
This can't be good.
Although we can turn the whole structure inside-out, that is, moving the double-for-loop inside every and each swith-case, it still won't be a satisfying solution.
So, the hackers used another way - dynamic compiling. Because they would know the actual arguments at runtime, they can directly put them into the instruction stream to make the method a specialized algorithm.
Charles Petzold actually wrote this in Chapter8 of "Beautiful Code". And he used C# to implement a highly efficient image filter, too.
On Nov 19, 10:11 pm, Mathias Gaunard <loufo...@gmail.com> wrote:
> The main reason image processing is slow in those high-level languages > is because often you can't have arrays of objects, only arrays of > pointers to objects. > Being able to store the objects themselves and not pointers to them is > required to write efficient code. And to do that, you need to specify > how an object is to be copied, moved etc. > Which makes C++ the only high-level language capable of being > efficient.
Java has char[], int[], etc. which don't impose any per-element storage overhead. C, D, Objective C and C# have that plus the ability to use unsafe indexing/pointer arithmetics. Of course the list of languages goes on and on.
None of the "high-level" languages gets close to "low-level" code using intrinsics mapping to SIMD instructions (available in some of those languages, but of course not as a part of the portable subset) in terms of performance except for the simplest cases; optimization is not just about flat arrays.
Specifications of copying, etc. are irrelevant in the context of most performance-critical data structures; you make bitwise copies of those. And when you don't, it doesn't mean that having the non-trivial copying protocol implemented in implicitly called functions with special call/definition syntax is "good" or "high-level".
On Nov 19, 10:11 pm, Yossi Kreinin <yossi.krei...@gmail.com> wrote:
> What I care about is the de-facto status. Porting from gcc 3 to gcc 4 > raises lots of problems of syntactic compatibility, for example; both > came out years after the C++ standard. All versions of VS, gcc and > Green Hills C++ I've used /crashed/ on quite simple C++ code.
It's interesting. You've mentioned that crash a few times already... Could you please recall what versions of the compilers you've used? Did you bother to report crash to them? And, most intriguing, what was the "quite simple C++ code" exactly, if it's not top secret? ;-)
> > Yep, and using virtual functions to iterate containers certainly have > > performance penalty over use of templates.
> If you do something non-trivial with the elements, it doesn't matter; > I was talking about these cases.
But if you do something "trivial" which might be otherwise inlined with templates your performance will suck. Or do you suggest using templates for "trivial" operations _and_ "virtual functions to iterate" in the "non-trivial" cases?
On Nov 20, 7:50 pm, Alex Shulgin <alex.shul...@gmail.com> wrote:
> > What I care about is the de-facto status. Porting from gcc 3 to gcc 4 > > raises lots of problems of syntactic compatibility, for example; both > > came out years after the C++ standard. All versions of VS, gcc and > > Green Hills C++ I've used /crashed/ on quite simple C++ code.
> It's interesting. You've mentioned that crash a few times already... > Could you please recall what versions of the compilers you've used?
Several (3-4), including very recent (built around 2006-2007).
It's not "that crash", it's "those many different crashes".
> Did you bother to report crash to them? And, most intriguing, what > was the "quite simple C++ code" exactly, if it's not top secret? ;-)
Today I definitely wouldn't bother to report front-end bugs of C++ compilers, but yes, I did "bother to report the crashes" as described below (BTW, of course in other cases the compilers didn't crash but instead silently produced the wrong code).
Green Hills sent patches, so I reported almost everything (their support is responsive; I heartily recommend them over "free" options such as cross-platform gcc/gdb/Eclipse combos, for example, but of course they have bugs as do all C++ tool chains).
With gcc, for each problem there was a newer version where it didn't occur; too bad I can't upgrade to a new version very easily because so many of the C++ syntax interpretation changes (I participated in upgrades from 2.95 to 3.1 to 3.3.1 to 4.1 to 4.2, and it was always lots of work). I didn't submit bug reports, since of course I wouldn't get a patch for the broken version; I did "report" one such case to this NG:
Check out the reply saying that 3.3.1 is outdated, and how I should switch to 3.3.5.
With VS, I didn't report the bugs at all (again, I wouldn't get a working patch for the version in question, and upgrading in the middle of a project would be hard, too). Of course VC++ 6 crashed, but so did newer versions (VS2003 and later, after the big rewrite of the MS compiler; it was my code/code I knew in projects by other people so I don't remember the full list of versions).
I won't start collecting/reinventing the bits and testing them with the respective versions of compilers and posting them - too much trouble. It was primarily, but not only, templates (no big surprise here, I suppose), several levels of complexity below what you see in boost and the like; the example I sent to the NG is a good illustration.
C++ is about 25-30 years old, depends on how you count. And this kind of thing still happens a lot. Yes, compilers have less disagreements about what C++ actually is in 2007 compared to 2003 compared to 2000, etc.; well, let's wait for the adoption of C++0x and see how much time it will take until the new features are supported correctly everywhere (although I expect this part of the language to be easier to get right than the existing parts).
One important thing about the whole business is the "root cause" of this, which IMO isn't "marketing of compilers", etc. but the real complexity of the language. If proficient compiler writers spend decades on figuring it out, how much time does it take a programmer merely using the language, and why does it have to be that way? Some people know some of the reasons, others simply say that "C++ is powerful and hence complicated". This argument is a misconception.
> But if you do something "trivial" which might be otherwise inlined > with templates your performance will suck. Or do you suggest using > templates for "trivial" operations _and_ "virtual functions to > iterate" in the "non-trivial" cases?
We're drifting away from the original context. All I said was that I'd like to have a uniform way to iterate over collections using virtual functions (it's easy to implement an abstract class Iterator and a template<class Iter> class IteratorImpl to provide dynamic interface to the statically bound operations of STL-style iterators; I just wish there was something standard along these lines). It was a minor remark somewhere in a message.
I didn't argue that everything should be done using virtual functions, just that sometimes it's convenient since you care about the recompilation of the complicated code iterating over the collection more than the run time penalty which may be dwarfed by the complexity of the other things in that code. Optimization of cases when the access to the elements of a collection is itself a bottleneck is a whole new discussion.
On Nov 20, 11:08 pm, Yossi Kreinin <yossi.krei...@gmail.com> wrote:
> With gcc, for each problem there was a newer version where it didn't > occur; too bad I can't upgrade to a new version very easily because so > many of the C++ syntax interpretation changes (I participated in > upgrades from 2.95 to 3.1 to 3.3.1 to 4.1 to 4.2, and it was always > lots of work).
Indeed, each new version of GCC tries to refuse illegal C++ syntax that it allowed before. Of course, you wouldn't have had to rewrite anything if your code was written in standard C++ and not in a non-standard dialect GCC used to accept.
> C++ is about 25-30 years old, depends on how you count.
On Nov 20, 6:55 pm, Yossi Kreinin <yossi.krei...@gmail.com> wrote:
> Java has char[], int[], etc. which don't impose any per-element > storage overhead.
Except what you want in your arrays isn't 'char' or 'int', it's a tuple, struct or record (which are all the same thing). You could get the same behaviour by making an array for each element of the tuple, but you would still suffer from loss of locality.
On Nov 21, 1:32 pm, Mathias Gaunard <loufo...@gmail.com> wrote:
> On Nov 20, 6:55 pm, Yossi Kreinin <yossi.krei...@gmail.com> wrote:
> > Java has char[], int[], etc. which don't impose any per-element > > storage overhead.
> Except what you want in your arrays isn't 'char' or 'int', it's a > tuple, struct or record (which are all the same thing). > You could get the same behaviour by making an array for each element > of the tuple, but you would still suffer from loss of locality.
The context of your remark was image processing, where you primarily deal with arrays of numbers (RGB images can be represented as flat uint8 arrays, for example).
However, C, Objective C, D and C#, among other languages, allow you to have flat arrays of structures.
On Nov 21, 1:32 pm, Mathias Gaunard <loufo...@gmail.com> wrote:
> On Nov 20, 11:08 pm, Yossi Kreinin <yossi.krei...@gmail.com> wrote:
> > With gcc, for each problem there was a newer version where it didn't > > occur; too bad I can't upgrade to a new version very easily because so > > many of the C++ syntax interpretation changes (I participated in > > upgrades from 2.95 to 3.1 to 3.3.1 to 4.1 to 4.2, and it was always > > lots of work).
> Indeed, each new version of GCC tries to refuse illegal C++ syntax > that it allowed before. > Of course, you wouldn't have had to rewrite anything if your code was > written in standard C++ and not in a non-standard dialect GCC used to > accept.
First of all, the fact that different versions crash on different things doesn't necessarily have to do with the fact that newer versions try to be more standard compliant; it simply means that newer versions fix bugs and add new bugs, which happens with any software. What I claimed was that C++ is very complicated, so the number of bugs in version x.y.z of a C++ compiler tends to be much larger than the number of bugs in version x.y.z of a compiler for another popular language, for all values of x, y and z.
Regarding compliance: I don't think it's very easy to prove that it's always "progress" (more standard-compliant behavior) rather than "regression" (less standard-compliant behavior). However, it mostly is "progress"; that doesn't make the problem go away though. It is virtually impossible to write standard-compliant C++ code if you don't have a tool verifying this automatically, so the situation where "you don't have to rewrite anything" is of purely theoretical interest.
Somewhat independently of that, of course there are cases where "more standard compliance" means more trouble with little or no benefits because of the way the standard is defined:
> > C++ is about 25-30 years old, depends on how you count.
> The first standard is 9 years old.
9 years is a lot of time. The fact that it took so many years to standardize is by itself an interesting data point regarding the complexity of the language.
:: On Nov 20, 7:50 pm, Alex Shulgin <alex.shul...@gmail.com> wrote: :::: What I care about is the de-facto status. Porting from gcc 3 to :::: gcc 4 raises lots of problems of syntactic compatibility, for :::: example; both came out years after the C++ standard. All :::: versions of VS, gcc and Green Hills C++ I've used /crashed/ on :::: quite simple C++ code. ::: ::: It's interesting. You've mentioned that crash a few times ::: already... Could you please recall what versions of the compilers ::: you've used? :: :: Several (3-4), including very recent (built around 2006-2007). :: :: It's not "that crash", it's "those many different crashes". :: ::: Did you bother to report crash to them? And, most intriguing, ::: what was the "quite simple C++ code" exactly, if it's not top ::: secret? ;-) :: :: Today I definitely wouldn't bother to report front-end bugs of C++ :: compilers, but yes, I did "bother to report the crashes" as :: described below (BTW, of course in other cases the compilers :: didn't crash but instead silently produced the wrong code). :: :: Green Hills sent patches, so I reported almost everything (their :: support is responsive; I heartily recommend them over "free" :: options such as cross-platform gcc/gdb/Eclipse combos, for :: example, but of course they have bugs as do all C++ tool chains). :: :: With gcc, for each problem there was a newer version where it :: didn't occur; too bad I can't upgrade to a new version very easily :: because so many of the C++ syntax interpretation changes (I :: participated in upgrades from 2.95 to 3.1 to 3.3.1 to 4.1 to 4.2, :: and it was always lots of work). I didn't submit bug reports, :: since of course I wouldn't get a patch for the broken version; I :: did "report" one such case to this NG: :: :: http://groups.google.co.il/group/comp.lang.c++.moderated/msg/6584bab8... :: :: Check out the reply saying that 3.3.1 is outdated, and how I should :: switch to 3.3.5.
So what exactly is wrong with the reply "We fixed that problem last year, please use the current version of the compiler" ?
On Nov 21, 10:51 pm, "Bo Persson" <b...@gmb.dk> wrote:
> So what exactly is wrong with the reply "We fixed that problem last > year, please use the current version of the compiler" ?
Here's an answer to your question, copied from my message which you quoted:
> :: too bad I can't upgrade to a new version very easily > :: because so many of the C++ syntax interpretation changes (I > :: participated in upgrades from 2.95 to 3.1 to 3.3.1 to 4.1 to 4.2, > :: and it was always lots of work)
You also asked me in another sub-thread why this sort of problem has to do with the language. I believe I answered you in that thread and repeated the case in this thread. To summarize, the problem is the complexity, which has two effects, among other things:
* It increases the amount of bugs in tools (complicated things are harder for the tool vendors to get right) * It makes it harder to upgrade to newer versions of tools (more things change across versions)
Of course there's no way to formally prove that this is a problem, and it's up to each person to "grade" the practical importance of problems happening in practice.
