5 ms·
On the other hand, C's treatment of arrays in general (not just strings) has unfortunate implications both for optimization and for future extensions. The preva
by benlorenzetti 9y ago
On the other hand, C's treatment of arrays in general (not just strings) has unfortunate implications both for optimization and for future extensions. The prevalence of pointers in C programs, whether those declared explicitly or arising from arrays, means that optimizers must be cautious, and must use careful dataflow techniques to achieve good results. Sophisticated compilers can understand what most pointers can possibly change, but some important usages remain difficult to analyze. For example, functions with pointer arguments derived from arrays are hard to compile into efficient code on vector machines, because it is seldom possible to determine that one argument pointer does not overlap data also referred to by another argument, or accessible externally. More fundamentally, the definition of C so specifically describes the semantics of arrays that changes or extensions treating arrays as more primitive objects, and permitting operations on them as wholes, become hard to fit into the existing language.
Ritchie notes the difficulty with optimization and aliasing and as far as I know the only portable C89/99 convention for this is using the appropriate function if what you want to do is memcpy() or memmove().
I love C and programming is mostly a hobby for me. But my language experience does not really extend beyond C and C++, other than reading about D, Lisp, Rust, etc. I also think the STL is the beautiful thing C++ gave us, and having it as a library is better than building these structures into the language. The STL relies heavily on iterators of course.
My question to HN is: do any languages that really emphasize pointers and iterators over arrays and indices have a non-cumbersome way of telling the compiler when no aliasing is expected? As a hobbyist, I am more interested in something like slices from D or parameter type restrictions than trivially obvious global guarantees like ``if you mutably borrow it then there is no aliasing''. Do D programmers find the slices helpful and easy? Is the syntax and/or semantics such that the programmer can provide the compiler with aliasing info? Are there a small number of type concepts for this or does it explode with the number of different data structures.
I know there is the restrict keyword, but I have always been too lazy to use it in C and even in C++ it seems (quadratically?) unlikely you would be energetic enough to properly declare which pairs of entities could not alias.
- dozzie 9y ago> I also think the STL is the beautiful thing C++ gave us, [...] It did not. STL was given to us by HP and SGI, and then C++ adopted STL into its standard library.
- pjmlp 9y agoAlexander Stepanov gave STL to ANSI C++ working group, after implementing it originally in Ada 83. What HP and SGI did was to provide the first C++ working implementations of it, outside the ANSI C++ working group work.
- lucidguppy 9y agoIt would be nice if the STL would be a common denominator across a few languages.
- pjmlp 9y agoWhen Java came out there were a few commercial offerings that were kind of "STL for Java", but with 1.2 Java got its own Collections API and the interest faded away.
- AnimalMuppet 9y agoBut, if I understand correctly, what HP and SGI did was basically to let Stepanov work on STL while he worked for them, and give some semi-official sanction for the STL releases. They didn't see the STL, decide that they needed to work on it, and set up an independent team to do so. And, if I understand correctly, Stroustrup saw the STL and said (paraphrased) "Yeah, that's going in."
- benlorenzetti 9y agoThanks dozzie and pjmlp, I should have credited Alexander Stepanov. He is a great programmer and educator that has impacted my CS education. What I meant was that C++ was the first widely adopted language that had memory access and sufficient generic features for the STL to be written and easily used.
- pjmlp 9y agoWell, Ada forces aliasing to be explicitly requested. You see an example here https://gcc.gnu.org/onlinedocs/gnat_ugn/Aliased-Variables-and-Optimization.html https://gcc.gnu.org/onlinedocs/gnat_ugn/Aliased-Variables-an... To use C vocabulary, Ada always assumes restrict unless you make use of aliased, and it is a compile error to handle it otherwise.
- benlorenzetti 9y agoWow Ada syntax is not what I'm used to! This is interesting; it seems like a very simple solution to make the problem less widespread. It is still on you though to use the correct version of the equivalents of memcpy() and memmove() though?
- pjmlp 9y agoAda has not stand still, the latest standard revision is from 2012. http://www.ada2012.org/ http://www.ada2012.org/ It has all the modern goodies in it, OOP, interfaces, contracts alongside type safety. Then if you really care about high integrity systems, there is its brother SPARK, which is a hardened version of Ada, the latest revision being from 2014. http://www.spark-2014.org/ http://www.spark-2014.org/ Regarding calling memcpy() and memmove(), the compilers should be able to produce the right kind of code. Now if you really mean the C functions, the aliasing declaration should be part of declaration. Not sure what is the current state of Ada's POSIX specification.
- kazinator 9y agoC99 introduced the restrict keyword by which the programmer promises that the pointer doesn't alias anything (or else the behavior is undefined). memmove versus memcpy only solves the problem for block moves, not for other array operations. Think about a Fast Fourier Transform or whatever where the compiler has to suspect that the inputs overlap in dumb ways.
- adwn 9y ago> My question to HN is: do any languages that really emphasize pointers and iterators over arrays and indices have a non-cumbersome way of telling the compiler when no aliasing is expected? Rust has this concept baked into the language: any mutable reference is statically guaranteed to not alias anything else that is accessible. Non-mutable references can alias each other, but I don't think there are any optimizations that could be inhibited by this.
- benlorenzetti 9y agoYeah, this is the gist of my question. Basically if programming language inc(C) has an overloaded function for both memcpy(alias...) and memmove(restrict...), how does the type information enter the system which allows the compiler choose the correct procedure? I'm interested in any language innovations that have a smooth, suave feature for this. Rust changes the default, but in some sense its not an absolute improvement; where C bluntly assumes memmove(), Rust bluntly applies memcpy().