Showing posts with label C++. Show all posts
Showing posts with label C++. Show all posts

Friday, May 29, 2015

Go, Rust, Python... some random impressions

During a discussion in the Italian Python mailing list, there were some comments about "C-family" languages and how they do compare to Python. As a consequence this post is partly a translation and partly a reworking of the opinions I expressed there. Since it is deprived of much of its context, some parts could not make too much sense; plus I suffer from a severe form of... well I tend to digress. So it might suck rat's ass, but there might be something interest, so bear with me. This post is neither meant to imply any inherent merit in being "similar" to Python nor to criticize any language. As a full disclosure, I love Python and quite like Go. Rust gave me a very good impression, too.

So, Rust syntax shows C influences (even though I feel like the main influence from the C family is actually C++ rather than plain C), but overall the influence of ML is much stronger, especially if we also consider the semantics. Why we ended up comparing Rust with Python is a pretty long story, which started from this post (and evolved here -- in Italian --; thanks Carlos). At the end, other languages were somewhat drawn in the comparison, including Go, C, C++, Java and a C# that is still under shock for having been freed but is alive and kicking nonetheless (my avoidance to make explicit what it is kicking is intentional). Actually, I revisited the thread and we also mentioned OCaml, Haskell, SML (that might have been my fault), Erlang , Elixir, F#, D, Nim (also my fault), Perl, Luc Besson (which is not a programming language, but does awesome movies), Ruby (the programming language), Clojure, Scala, even PHP (oh, well, this blog was supposed to be PG13) and Ceylon (which I did not even know it existed: either I am getting old or people are creating too many languages). Sadly nobody mentioned Lisp or Scheme and surprisingly nobody mentioned Javascript. If your favorite language is not listed here, add a comment. At the end of the day much of the discussion involved Python, Rust, Go, Java and C++, which was to be expected.

Rust and Python

All considered, I feel like Rust is philosophically one of the farthest languages from Python. Again, this is not a bad or a good thing; it is the way things are.

Static vs. Dynamic typing

Python is entirely on the dynamic side of typing. It does not support static typing at all, not even the new Python type hints go in that direction. See especially this paragraph for more context: it is always going to be only runtime checks, and they are meant to be entirely optional (even by convention) even if some linters could make use of it. Even then, hints are meant to be used for duck-typing (i.e., to hint that methods take a Number rather than specifically requiring an int). Most languages in the C family are based on static typing and features in the direction of dynamic typing are incomplete, missing and always frowned upon (think about designing Java interfaces working with Objects instead of  interfaces).

Early binding vs. static binding and dynamic dispatch vs. static dispatch

Again, Python is completely dynamic and late bound. Everything is bound at the latest possible moment. If it were possible to bind calls after the process terminated, Python would do that.
The other languages we are considering here have significantly different approaches among themselves: Java uses dynamic dispatch/late binding; Go uses dynamic dispatch when methods are called on an interface, static dispatch when called on a struct. C++ by default uses early binding and static dispatch. When virtual is explicitly used, dynamic dispatch is used. Rust provides both static and dynamic dispatch: to get dynamic dispatch a trait object has to be used. General consensus (and standard library design) favor static dispatch any time that it is possible and it makes sense.

Object model

The object model of Rust (which technically speaking does not claim to be an OO language, so here we are a bit overloading the term) is remarkably different from classic imperative object oriented languages (e.g., Python, Java, C++). Python, Java and C++ also have massively different object models, but in a sense they are closer to one another than Rust is. On a superficial analysis traits seem to behave somewhat like interfaces, but I feel the differences are really deep. They are much closer to Haskell type classes or ML modules; I do not have much experience with Rust, but designing stuff with Haskell type classes is much different from designing stuff in Java (or Python). Really. As a side note, when trait objects are used, the behavior is rather similar to Go interfaces: the difference is that interfaces in Go are implicitly implemented, while in Rust you have to explicitly implement the traits. Go does not provide anything similar to Rust traits when used statically (there are huge discussions on Go lack of templates and related stuff, won't repeat it here).

Pragmatics

Python philosophy is to keep things as simple as possible and to abstract details away (especially low level details). On the other hand Rust was created with the idea of giving full control over low level details. If you do not want to do it (or do not have to do it) Rust might feel like an overkill. There might be still tons of reasons to use it, though.

Runtime

Python has a very rich runtime. In fact, it is so rich that entirely reasonable optimizations are completely impossible by design (unless you are extremely smart about it: see for example the fact that the function frame is an object and technically you might end up accessing it in some call downstream, so a lot of stack related optimizations are not really feasible -- note to self: check what Pypy guys do about it). Rust, on the other hand, almost does not have a runtime by design. The runtime is really minimal by deliberate choice (which makes a lot of sense considering the target)
Just to wrap it up, if I have to pick a single language in the C family to be closer to Python esthetics, that would be Go (with a honor mention to C itself). Both want to abstract the irrelevant details and the system (in one case the VM, in the other the compiler + runtime) does "the right thing". Both have similar issues when you need to go outside the box and need more control (FFI + cython on one side, unsafe + low level syscalls + FFI in the other).
On the other hand, Rust is much closer to C++ or OCaml: it is a rather complex language that enables fine-grained control on everything; however, it is often hard to relinquish such control: truth to be told, it seems that Rust is much better in this area, the model is simpler to reason with and saner, so the net result is that even if you can exercise a lot of low level control, it is not as painful as in C++, where sometimes the abstractions are all wrong.

Go and Python

Another important similarity between Python and Go is that after few weeks of study (days? depends on how fast one is to learn a programming language) it is feasible to read and understand all the code out there. If something is unclear, it is because of lack of familiarity with the domain (e.g., low level networking details) but not because of complex or unusual language features or magic.
If possible, Go is even more extreme in this than Python itself. There are rather basic concepts in Python that lots of coders do not understand and do not know how to use. Albeit I disagree, lots of people consider hard stuff like meta-classes, the descriptor protocol, coroutines implemented with generators and even the relatively simple decorators.
In Go there are no features with a comparable level of cognitive overhead: the language is extremely simple. You get few basic blocks with very simple semantics that can be composed to obtain arbitrarily complex effect. The net result is that even if the newbie might not know how to compose the blocks to get the intended result, he would still be able to understand a solution created by a more experienced programmer, understand which does what and why. This does not mean that writing in Go is necessarily simpler than writing in Python, just that it might be even simpler to read.

Other languages (such as C++, OCaml, Haskell and perhaps Rust) need much more understanding to be able to cover the same amount of code. To be entirely sincere, I have dabbled with Haskell for about ten years and to this day there is a lot of code that I need to unwrap, disassemble and study line by line to actually understand how it is working (what is doing is somewhat simpler, but appreciating the nuances of the language takes time). With Go I was reading the standard library implementations after 2 days.

In fact, when I fell for Python I was mainly using other stuff (including, stuff like Perl and C++). I used to mock lots of Python tenets. Then a guy I knew from some usenet group asked me to review a couple of his scripts. That was before github, before git was even imagined. It was a world of pain and CVS, and SVN was brand new and people often sent code via email and similar primitive means. But I am digressing... I knew something about networking, back then. Did not know Python at all, though. I was dubious that I could actually help him out; but then I realized I was perfectly capable of reading his code, without having ever written a line of Python, without even having read a tutorial, I might say, without even having read the wikipedia page of Python. Which would be surprising now, but really, back then Wikipedia was probably hosted on something less powerful than my mobile phone (and loading pages took tens of seconds, sometimes minutes). Nonetheless I could read and immediately understand the scripts. I could also easily modify them and make them work. Go is the second language after Python that gave me the same impression, which was the decisive factor in my decision to give it a deeper look.

Rust and Python (again): what about the juniors?

Back to the comparison between Rust and Python... one of the points raised in the discussion was whether some freshly trained junior Python programmer could easily take on Rust. To put a disclaimer here, the archetype of said programmer is not the smart college guy that will end up working for some IT colossus or über-cool startup, nor the garage hacker without formal education but with talent and brains in spades. It is more like the average IT guy, mildly skilled, mildly cable that can, with some supervision, work on a relatively trivial project with other people. To my surprise, there seem to be a lot of these guys. So... the question is, if one of such guys is trained in Python, which language from the C family can he more easily pick up?

The idea I have of Rust, is that it is not the language for him. I believe said novice would probably not even understand where to start. Lots of design decisions in Rust hold that some problems need to be solved in the most efficient way, so the language should provide the programmers control to specify everything to get to that most efficient way. The side effect is that somebody without experience in systems, low level programming and computer architecture would not even know that the choices Rust provides are solutions of real problems. Essentially, I am afraid, a lot of it would be taken just as magic, not as conscious trade offs between control and ease of programming. This is not a critique to Rust: I appreciate a lot its coherence to its goals. Among them there is not "being a language for unskilled novices".

I am also not suggesting that Java would be the best candidate here (really, I have no clues), but to make a comparison to write decent (not excellent, plainly decent) Java it is sufficient to have an adequate understanding of object oriented design. Essentially, it is quite impossible to write sensible Java without a solid understanding of object oriented programming (at least, of the flavor of OOP that Java promotes). And, on the other hand, with a solid understanding of OOP, the resulting Java tends to be fine (again, not perfect, not super smart or super efficient, but fine). The standard library is rich and well documented and there are widely used libraries that cut the few corners that were left (e.g., Guava, Apache Commons, Netty, etc.). So probably somebody with experience in Python and a decent understanding of the OOP part could be able to design in Java software that does not make me want to puke. Too much. And yes, a lot more needs to be taken into account to write great Java code (and the JVM is a tiny operating system on its own that needs to be understood, albeit that might be easier than getting the same level of understanding of the whole Posix model).

I would be very interested in seeing with would happen with Go. Probably the language is too young to spread in those contexts, but I would still love to see whether the transition from Python to Go is really as easy as it seems.

At the end of the day, the impression Rust left me (after a couple of days of study... so I might still be partial) is that of a language closer to a sensible version of C++ that does not drive people to Lovecraftian abysses of insanity and pain. The comparison is a huge stretch: I am talking about feelings here, not objective features. Rust is effectively much more functional than OOP and it does not really work "like C++". It does not at all. Again: the keyword here is "feeling". Also Rust is immensely agile for a language that offers such an astonishing level of detail on low level semantics.

On the other hand, Go seems as perfectly in between C and Python: it can be seen as a modernized C, or like a super-optimized Python. Go get it!



Monday, February 20, 2012

Lion, brew and gcc

For me, the transition to lion was relatively painless. Painless here basically means that I patched up the couple of things that gave me problems . In the specific situation, the issue is that Apple's new developer's tools do not include regular gcc anymore. Instead there is a version working with llvm backend which is great but has some issues with some packages that have not been updated yet.

Another problem is that is closely related is that I had a Python 2.7 installed with Python main website package. I did this because older OS Xs did not have Python 2.7. That Python was built with the older gcc-4.0 apple shipped with SL. Thus, new libraries I install with pip still want that compiler, which apple moved in /Developers-3.2.x/... Thus, I lived so far adding that directory to the PATH and happily compiling.

What I should have done was getting rid of my beloved python and either use EPD or Apple built-in 2.7 (shipping with Lion) or use a brew-ed python or see if Python.org distributes a Python compiled with the new compiler (which, as far as I know, is perfectly capable of building Python). The question is: are there any python extension I need that need the older gcc? But this is not something I'm going to discuss here: not yet ready to make the transition.

I just want to point out that I installed the old gcc from homebrew-alt, and now I can just brew install --use-gcc for packages that need the old gcc compiler. This is easy to use and nice. I also removed the old Developers and hope everything's fine.

% git clone https://github.com/adamv/homebrew-alt.git /usr/local/LibraryAlt
% brew install /usr/local/LibraryAlt/duplicates/apple-gcc42.rb

An older version of gfortran I installed conflicted, but the commands above worked like a charm after removing it.

Saturday, July 23, 2011

Atkin for everyone (benchmark)

How I got here is quite a long story. However, I'm benchmarking trivial implementations of the Atkin sieve with different programming languages/implementations. Why the "trivial implementation"? Because:

  1. I did not want to spend to much time to write clever ones in each language
  2. Because otherwise half the benchmark would have been about my specific optimization skills (platform internals knowledge etc.) in each language
  3. I'm lazy

So... we try not to put too much importance on unimportant things and draw some interesting conclusions. First, as a comparison I use a very fast C implementation of the atkin sieve which I found here. This is the bottom-line. It is a cleverly implemented version in a fast language. I do not expect anybody to get close.

It is almost unbetable:

% time primes 1 10000000 > /dev/null
primes 1 10000000 > /dev/null 0.07s user 0.00s system 97% cpu 0.070 total

Consider that I had to suppress the output because this one not only computes the primes, but it also prints them.

Quite interestingly an unoptimized Java implementation is just above 100 milliseconds. Ok, I did not write every number on standard output. C still is faster. The point is that the Java code took like 10 minutes to be written and is compared against a carefully crafted implementation in a language considered to be faster. This is a "good enough result" for Java (and it shows some excellent compiler work behind that). Both Java and C had to find the primes below 10000000. This is also what I did with the other languages.

Python

This is a kludge I used to test both regular Python (using numpy, which should provide a reasonably fast buffer to support the sieve) and Pypy, which should JIT to death integer computations.

I found quite interesting that using on not using numpy does not change things much. Regular Python took  6.16s without numpy and 6.12s with numpy. This makes sense: afterall, numpy is fast if used matrix-wise. In this case, however, I'm doing things element-wise. Perhaps I should devise a pure matrix manipulation implementation and benchmark that instead.

Pypy is surprisingly good: it takes 1.20 seconds to run the 10000000 numbers computation.

Javascript

Recently I got lots of interest in Javascript (especially thanks to the wonderful Javascript: the good parts, and the fact that about every piece of software I'm using nowadays is scripted in Javascript). So I decided to compare node.js/v8 as well. Writing the code was quite easy, even though Javascript has quite too many quirks for me to really like it. The virtual machine is impressing: less than one second (0.88) for the whole computation.

I have also to say that perhaps this benchmark is more in favor of Pypy than of v8, considering the huge amount of resources behind v8, compared to the resources behind pypy. Moreover, I find uncomparably more confortable to work with Python that with Javascript.

Clojure

After testing Java, the natural candidate is Clojure. How much inefficiency does the clojure runtime add? The code I wrote is voluntarily unclojurish and is more a direct translation from Java to clojure, exactly because now the focus is on the overhead. Apparently there are some big problems.

The first version I wrote did not involve the int coercions that the present version has and took about 2.8 secs. Replacing loops with doseqs made it slower (to about 3.x secs), so I went back to the explicit loop version. After that adding and removing coercions made times vary. Some coercions slowed things down, some sped them up. Another funny thing (logical, in fact) is that it is not true that a given coercion always speeds things up: for example the coercion on n1 was an improvement only after I also coerced end. For no reason I could fathom coercing n2 and n3 makes things worse.

In fact the presented version takes 1.5-1.6 seconds. However, adding the coercion on n2 makes the whole thing jump to 2.7 seconds. While for other coercions I understood why thing actually got worse, in this case I just don't know what to think.

Moreover, uncommenting the count-primes function call, makes the timing for atkin jump at 2.2 seconds. I think I plainly admit my incapacity to optimize clojure code: the logic behind its behavior just evades me.

Technorati Tags:

"JavaScript: The Good Parts" (Douglas Crockford)

Thursday, August 12, 2010

Atomicity and files

We all greatly value atomic operations. Either they fully succeed or they completely fail. Even better, if they fail, it is like they never occurred, so that it is not necessary to clean things up.

The term itself is widely used in the database community (the A of ACID stands for Atomicity) and in the parallel computing community. The meaning is essentially very similar, though the scope is different. Moreover, the idea is pervasive in computer science.

Writing exception safe code in C++[0] is essentially a strive for atomicity. C++ code is strongly exception safe if it has rollback semantics. That is to say failed operations have no side effects and consequently leave all data as it never happened. More details here [1]. It is usually considered extremely expensive to write all the code to be strongly exception safe.

In languages such as Clojure this comes for free. Memory is transactional[2], that is to say, it support the ACI (without D) properties of a relational database. Of course durability is not an issue: we are dealing with memory, after all. This is not extremely expensive as, by default, variables in Clojure are not modifiable. Essentially they are but names of const object. If a variable needs to change its value, vars, refs or atoms (but they are an entirely different story) must be used. And they are governed by a software transactional memory system [3].

Another famous source of atomic operations, is the POSIX standard. Some system calls are guaranteed to be atomic. In the following, we are mostly concerned with open (2)[4] and rename (2)[5].

In the open(2) system call, the check for the existence of the file and the creation of the file if it does not exist shall be atomic with respect to other threads executing open() naming the same filename in the same directory with O_EXCL and O_CREAT set.
For this reason, open can be used to implement concurrency structures such as locks; the link (2)[6] system call is often used as well. Moreover, the open function shall be used in Easier to Ask Forgiveness (EAFP) strategies [7], which are fare more secure and effective because open is atomic.

Unfortunately for us, the write(2) [8] system call is only partially atomic. That is to say if the requested write is “small enough” (that is to say the number of bytes are < PIPE_BUF), then the single write action is atomic. If this is not the case, the write is not atomic. Moreover, multiple write actions are, of course, not atomic.

To make things even worse, the whole open-write-close thing is not atomic at all. And is destructive. The typical problem is that when you open a file with O_TRUNC (or with something which in turns calls an open with O_TRUNC set) you destroy the content of the file. However, you may have successive errors which prevents the correct and complete writing of the new file. The typical solution is using temporaries.

References

[0] “Strive for exception safe code”, Effective C++, 3rd ed, S. Meyers, Addison-Wesley, pp. 127-134
[1] http://www.open-std.org/jtc1/sc22/wg21/docs/papers/1997/N1077.asc
[2] http://clojure.org/refs
[3] http://en.wikipedia.org/wiki/Software_transactional_memory
[4] http://www.opengroup.org/onlinepubs/009695399/functions/open.html
[5] http://www.opengroup.org/onlinepubs/009695399/functions/rename.html
[6] http://www.opengroup.org/onlinepubs/009695399/functions/link.html
[7] Python in a Nutshell, 2nd ed., A. Martelli, O’Reilly Media, pp. 134-136
[8] http://www.opengroup.org/onlinepubs/009695399/functions/write.html

Sunday, April 23, 2006

Quicksort (C and Python)

The quick-sort algorithm

Quick-sort is a sorting algorithm developed by Hoare that in average does O(n log n). The O() notation means that if the list length is n, the number of operations used to sort the list is in the order of magnitudo of n log n (in this case).

To be more formal, we shall say that there exist two constants c1 and c2 such that the number of operations m isc1 * n * log n <= m <= c2 * n * log n. Notice that c1 and c2 are not specified in the O notation
We stop with math here. If you want more precise informations about the O notation read the wikipedia.

Now I'm going to briefly explain the quick-sort algorithm, and then we will use that algorithm to exploit the expressive power of some programming languages. Keep in mind that more expressive does not necessarily mean faster to run. It means faster to write. But being faster to write means that we can try more efficient algorithms, thus improving performance in a more effective way.
Expressive languages are usually high-level. In fact we can also profile the code, track the bottleneck and rewrite only a couple of functions in C or in ASM. This lead to fast programs with fast development cycles.

Quick-sort strategy

Quick-sort uses a divide and conquer approach. We divide a list in two sublists using a pivot element. All the elements less than the pivot come before it, those greater after. Then we recursively apply quick-sort to the two sublists.
Notice that the pivot is chosen arbitrarily. Some implementations chose the first element of the list. Some chose it randomly, some use other criteria.
Moreover there are implementations of quick-sort that sort the list in place (that is to say memory used is bounded), some need extra storage. Guess which are the more efficient.

On wikipedia you can find more informations about the quick-sort algorithm. You can find also some implementations, and a link to a page full of implementations in different languages.

I almost did not write code. I took code from the wikipedia or around the web and I'm going to comment it. This is the "new" work I did. Comments, explanations, not code. I also wrote a couple of implementations, however I don't remember which ones.

Python

2.4.2 (#1, Mar 23 2006, 22:00:44)  
[GCC 4.0.1 (Apple Computer, Inc. build 5250)] 

Now lets examine a Python high level implementation.

def qsort(L): 
    if L == []: return [] 
    return qsort([x for x in L[1:] if x< L[0]]) + L[0:1] + \ 
            qsort([x for x in L[1:] if x>=L[0]]) 

This is the exact description of the quick-sort algorithm, if you know what Python list comprehension are. When I write [x for x in L if p(x)], Python computer the list of elements of the L container that make p(x) true.

L[a:b] is the sublist of L[L[a], L[a+1], ..., L[b-1], L[b]]. L[a:]==L[a:len(L)], L[:b]==L[0:b]

[x for x in L[1:] if x< L[0]] is the sublist of the elements of L a part from the first one (that is the pivot) such that x is less than the pivot (L[0]).

[x for x in L[1:] if x>=L[0]] is the sublist of the elements of L a part from the first one (that is the pivot) such that x is greater or equal than the pivot (L[0]).

Then we pass those sublists to qsort that recursively sorts them, and eventually we return a append all those sublists and return them.

This implementation, although beautiful to read and understand is horrible from a performance point of view. It creates, concatenates and destroys a large number of lists. Moreover it is purely recursive. For large lists, we can even exhaust the stack space.

A version of quick-sort in Python that has no need for more memory is this:

def partition(array, begin, end, cmp): 
    while begin < end: 
        if cmp(array[begin], array[end]): 
            (array[begin], array[end]) = (array[end], array[begin]) 
            break 
        end -= 1 
    while begin < end: 
        if cmp(array[begin], array[end]): 
            (array[begin], array[end]) = (array[end], array[begin]) 
        break 
        begin += 1 
    return begin 
    
    def sort(array, cmp=lambda x, y: x > y, begin=None, end=None): 
        if begin is None: begin = 0 
        if end   is None: end   = len(array) 
        if begin < end: 
            i = partition(array, begin, end-1, cmp) 
        sort(array, cmp, begin, i) 
        sort(array, cmp, i+1, end) 

[NOTE: code has been reformatted without running it again: it is likely
to be wrong!]

If you want to run this code, remember that in Python indentation matters. If you just copy and paste the code, you may end with unusable code.
Anyway, I benchmarked all of them. "Elegant quicksort" is the first implementation. "Standard quicksort" is the latter. "Bultin sort" is standard python sort algorithm (that is not a quicksort, but a dedicated sorting algorithm).

Elegant qsort: [21.20, 19.75, 20.08, 20.46]
Builtin qsort: [1.61, 2.29, 2.29, 2.29]
Standard qsort: [31.15, 30.60, 30.68, 30.38]

Probably due to heavy optimization performed in list comprehension the "elegant" algorithm is faster than the standard one. [from the future: I hardly believe that]. However both of them are more than ten times slower than the python built-in sort algorithm.
We have learnt:

  1. High level languages are great to express algorithms in a readable way (and we can use them to test them and see how they work and all)
  2. You should not implement "basic" algorithms in high level languages: use their built-ins or write them in C (most built-ins are written in C).

C

Now it is time for a couple of pure C quick-sort:

void qsort1(int a[], int lo, int hi ){ 
    int h, l, p, t; 
    if (lo < hi) { 
        l = lo; 
        h = hi; 
        p = a[hi]; 
        do { 
            while ((l < h) && (a[l] <= p))  
                l = l+1; 
            while ((h > l) && (a[h] >= p)) 
                h = h-1; 
            if (l < h) { 
                t = a[l]; 
                a[l] = a[h]; 
                a[h] = t; 
            } 
        } while (l < h); 
        t = a[l]; 
        a[l] = a[hi]; 
        a[hi] = t; 
        qsort( a, lo, l-1 ); 
        qsort( a, l+1, hi ); 
    } 
} 

Another implementation is:

void quicksort(int x[], int first, int last) { 
    int pivIndex = 0; 
    if(first < last) { 
        pivIndex = partition(x,first, last); 
        quicksort(x,first,(pivIndex-1)); 
        quicksort(x,(pivIndex+1),last); 
    } 
} 

int partition(int y[], int f, int l) { 
    int up,down,temp; 
    int piv = y[f]; 
    up = f; 
    down = l; 
    goto partLS; 
    do {  
        temp = y[up]; 
        y[up] = y[down]; 
        y[down] = temp; 
        partLS: 
        while (y[up] <= piv && up < l) { 
         up++; 
        } 
        while (y[down] > piv  && down > f ) { 
            down--; 
        } 
    } while (down > up); 
    y[f] = y[down]; 
    y[down] = piv; 
    return down; 
} 

C also have a builtin quick-sort, that is much more advanced than this ones, since it allows to specify a comparison function, thus working with all kinds of data types.

Benchmarking these was hard. They too fast to be benchmarked with a list of a million elements and the standard posix clock function. However if you want to run the bench yourself, I could not use MacOS X specific bench functions.
So I used a list of 100000000 elements.
This is the (ugly) code I used for benchmarking. The test is not really interesting. Of course since C integers are machine integers it is dramatically faster than other solutions. It could have been more interesting if we sorted other data structures, where the gap could be reduced.

#include <stdlib.h> 
#include <stdio.h> 
#include <time.h> 
#include "qsort1.h" 
#include "qsort2.h" 
#define LEN 100000000 

int intcmp(const void *a, const void *b){ 
    return *(int*)a - *(int*)b; 
} 

int main(){ 
    size_t index; 
    int *l = malloc(sizeof(int)*LEN); 
    clock_t last, current; 
    srand(time(NULL)); 
    for(index = 0; index < LEN; ++index){ 
        l[index] = rand(); 
    } 
    
    last = clock(); 
    qsort(l,LEN, sizeof(int), intcmp); 
    current = clock(); 
    printf("C qsort: %f\n", (current-last)/(float)CLOCKS_PER_SEC); 
    
    for(index = 0; index < LEN; ++index){ 
        l[index] = rand(); 
    } 
    last = clock(); 
    qsort1(l,0, LEN-1); 
    current = clock(); 
    printf("int qsort: %f\n", (current-last)/(float)CLOCKS_PER_SEC); 
    for(index = 0; index < LEN; ++index){ 
        l[index] = rand(); 
    } 
    last = clock(); 
    quicksort(l,0, LEN-1); 
    current = clock(); 
    printf("qsort 2: %f\n", (current-last)/(float)CLOCKS_PER_SEC); 
    free(l); 
    return 0; 
} 

Wednesday, April 5, 2006

Investigated iMac Troubles: not a faulty scheduler but something related to memory

Some time ago I stated multitasking of Mac OS X Intel was bugged. Under some conditions (which at the time I hadn't discovered) the GUI hung (something I never saw on tre MacOS before) and all the system slowed down terribly.

Computations

I anticipate here: the problem I found is real. MacIntel seem to have problems when large quantities of RAM are allocated. It is not a problem with the scheduler. In fact the system simply slows down as a whole.
The fist thing I did was to write a simple program trat stressed CPU and made a lot of I/O and at tre same time allocated and deallocated small quantities of memory in a quite inefficient way. However tre system was not slowed in any perceptible manner.

this is tre post where I spoke about trat program.

Here I add some benchmarking. Now I have to describe tre machines involved. Of course tris not a PPC vs. Intel bench. Unfortunately tre most powerful PPC machine is a notebook, and we can't expect to compete with the iMac. What I want to show are tre relative values between them.

Machines


Model

CPU

Clock

RAM

Bus

Hard Disk

PowerBook G4

G4 (Single Core)

1.5 GHz

512 MB

167 MHz

5400 rpm

iMac CoreDuo

Intel CoreDuo

2.0 GHz

1.5 GB

667 MHz

7200 rpm


big_matrix

This the test I described here
I compiled the test with no optimizations. This is probably a mistake.
The full test on the iMac took more than twenty minutes (matrix 500x500). The Mac was usable and had no slowdowns:
time ./big_matrix  
real    20m39.110s 
user    12m10.943s 
sys     7m46.112s 

Reducing the matrix size to 100x100 with no optimization the result is
time ./big_matrix 
real    0m9.683s 
user    0m5.805s 
sys     0m3.688s 

Compiling with the -fast option did not change things much, nor did -O3 or -Os (as I said the code was intended to be quite inefficient, I'm not surprised compilers weren't really able to optimize). However explicitly activating -mmmx-msse-msse2-msse3 gave a little improvement (about 5%, that could even be a statistical variation).

As I said before the most important thing is however achieved: the mac remains perfectly usable.

For those who are interested in this sort of things, the powerbook took about an hour and an half. However optimizations improved speed by a full 10% (which is quite acceptable, indeed). However I'm sad it performed so badly. I should investigate why altivec did not work properly (If it did, I suppose it should do something more that 4 times and more slower than the Intel).

Keep in mind that my software wasn't designed to work on multiple threads (This could be an interesting addition, thought). However the system kept on swapping it between the two cores, avoiding many possible optimizations.

Wonderings...

Now only very large allocations remained to do. So I wrote this small (idiotic) software.

Basically it takes a filename as a command line argument, finds out the dimension of the file with a stat syscall, allocates enough space to hold it and then fills the buffer. If the file is big enough this (a part from being terribly inefficient) allocates a lot of RAM.
I called it on a 985 MB file (that means the software allocated 900 MB of real memory, since it is not only allocated, but filled too).

$ ls -lh ../../Desktop/Ubuntu_510.vpc7.sit  
-rw-r--r--   1 riko  staff        985M 12 Feb 03:13 ../../Desktop/Ubuntu_510.vpc7.sit 

The file is loaded correctly and this is the time bench.

$ time ./load_file ../../Desktop/Ubuntu_510.vpc7.sit  
real    3m31.010s 
user    0m0.001s 
sys     0m4.062s 

This value is really variable. Another time it took only 1m42s.
And... the Mac slowed down. I know that such a program is idiotic. However it was one of the quickest way to understand how behaves the iMac when someone needs a lot of RAM (this could be a memory leak, for example).
In fact in some cases the mac remains slowed down for a while, until RAM is truly released and other processes are paged in.

#include  
#include  
#include  
#include  
#include  
#include  
#define BUFFER 2<<22 

int main(int argc, char *argv[]){ 
    char *mem; 
    int fd; 
    size_t pos = 0, res=0; 
    off_t sz; 
    struct stat st; 
    stat(argv[1], &st); 
    sz = st.st_size; 
    
    mem = (char*)malloc(sz); 
    fd = open(argv[1], O_RDONLY, 0); 
    
    while( (res = read(fd, mem + pos, BUFFER) ) != 0){ 
        pos+=res; 
    } 
    
    close(fd); 
    free(mem); 
    return 0; 
} 

As you may notice, this makes no check on sanity of the buffer allocated by malloc. Don't use it on a 4 GB file, it will probably crash.
When I run this very test on the Powerbook I was prepared that the results would have been terrible. In fact the powerbook does not have 1 GB free ram. It does not even have 1 GB RAM. It has only 512 MB. That means that allocating and filling 1 GB relies heavily on paging (and makes a lot of disk accesses to swap in and out pages of memory).Keeping this in mind, the results have been quite good (and more stable, in fact sometimes the iMac performs worse than the pb, that has 1/3 the RAM.). I would like that someone with 1.5 GB or 2 of RAM would try this.

$ time ./load_file ../aks_old/nr.bkp  
real    3m31.526s 
user    0m0.002s 
sys     0m7.728s 

Moreover the file used was slightly bigger. So it took about the double of the time (keeping the best iMac performance) or quite the same time (keeping the worst), but with a very big hardware handicap. Astonishing. This can also be interpreted saying that something slowed down the iMac considerably.
I didn't mention it before. Although slightly slowed, the PowerBook was quite responsive and usable during the test, while the iMac was not.
I/O Only
I rewrote the software above to read the file in a smaller buffer of memory instead of keeping it all in memory. This is the source code:

#include  
#include  
#include  
#include  
#include  
#include  
#define BUFFER 2<<22 
int main(int argc, char *argv[]){ 
        char *mem; 
        int fd; 
        size_t pos = 0, res=0; 
        off_t sz; 
        struct stat st; 
        stat(argv[1], &st); 
        sz = st.st_size; 
        mem = (char*)malloc(BUFFER); 
        fd = open(argv[1], O_RDONLY, 0); 
        while( (res = read(fd, mem, BUFFER) ) != 0); 
        close(fd); 
        free(mem); 
        return 0; 
} 

The speedup is amazing.

$ time ./read_file ../../Desktop/Ubuntu_510.vpc7.sit  
real    0m28.007s 
user    0m0.001s 
sys     0m1.472s 

Some other times I got about 17s. I should investigate this variance. However, the system did not slow down at all and remained perfectly usable. That makes me thing the problem does not concern I/O, but memory.
The powerbook performed like this:

$ time ./read_file ../aks_old/nr.bkp  
real    0m47.194s 
user    0m0.002s 
sys     0m3.833s 

Memory only...

The last step is writing a stupid software that only allocates large chunks of memory. I made it allocate (and release) progressively larger chunks. First of all this demonstrates the issue does not regard memory leaks only.
Applications that allocate big quantities of RAM in large chunks are slowed. You can also see that the mac slows down (and the allocation time increases) the more the block gets bigger.

#include  
#include  
#include  
int main (int argc, const char * argv[]) { 
    unsigned long size = 2; 
    unsigned long i; 
    int *mem; 
    
    while(size * sizeof(int) 0){ 
        mem = (int*) malloc(size * sizeof(int)); 
        if (mem==NULL) break; 
        printf("Allocated %u bytes\n", size * sizeof(int)); 
        for(i=0; i < size; ++i) {
            mem[i]=i; 
        } 
        free(mem); 
        mem=NULL; 
        printf("Deallocated %u bytes\n", size * sizeof(int)); 
        size*=2; 
    } 
    return 0; 
} 
I also wrote a version that only cycles through variables without allocating. It took less than half second to run, so it's not cycling that affects performance in the software. The first time I run it with not so large chunks. The computer remained quite responsive. Then I run it with full chunks. And it was a hell. In the 1 GB allocation the computer was plainly unusable, not to speak about the 2 GB. However the machine was much more usable than in the I/O + memory test.
time ./memory_allocator  
Allocated 2 bytes 
Deallocated 2 bytes 
[SNIP] 
Allocated 536870912 bytes 
Deallocated 536870912 bytes 
real    0m43.940s 
user    0m9.196s 
sys     0m9.137s 
time ./memory_allocator  
Allocated 8 bytes 
Deallocated 8 bytes 
[SNIP] 
Allocated 1073741824 bytes 
Deallocated 1073741824 bytes 
Allocated 2147483648 bytes 
Deallocated 2147483648 bytes 
real    0m36.538s 
user    0m9.181s 
sys     0m8.851s 

Small allocations

At this point I wrote a program that did smaller allocations. You can see that what matters is the quantity of ram allocated. The very same task, when the process has allocated more than 1 GB is significantly slower.
[Starting software] 
utime: 566              stime: 4198 
[Allocated first chunk] 
utime: 20               stime: 30 
[Populated first chunk] 
utime: 117010           stime: 558634 
[Allocated second chunk] 
utime: 27               stime: 50 
[Populated second chunk] 
utime: 132365           stime: 12 
[Allocated third chunk] 
utime: 38               stime: 487 
[Populated third chunk] 
utime: 229719           stime: 10 
[Allocated fourth chunk] 
utime: 22               stime: 41 
[Populated fourth chunk] 
utime: 228182           stime: 880172 
* Freed first chunk. 
* Freed second chunk. 
* Freed third chunk. 
* Freed fourth chunk. 
 
utime: 79               stime: 2 
and the software was:
#include  
#include  
#include  
#include  
#include  
#include  
void puts_rusage(){ 
        struct rusage ru; 
        static struct timeval slast = {0, 0}; 
        struct timeval scurrent; 
        static struct timeval ulast = {0, 0}; 
        struct timeval ucurrent; 
        getrusage(RUSAGE_SELF, &ru); 
        ucurrent = ru.ru_utime; 
        scurrent = ru.ru_stime; 
        printf("utime: %ld\t\tstime: %ld\n",  
                        ucurrent.tv_sec - ulast.tv_sec,  
                        scurrent.tv_sec - slast.tv_sec 
                        ); 
        ulast = ucurrent; 
        slast = scurrent; 
} 
int main (int argc, const char * argv[]) { 
unsigned long size = 2<<26; 
unsigned long i; 
int *mem1; 
int *mem2; 
        int *mem3; 
        int *mem4; 
        puts("[Starting software]"); 
        puts_rusage(); 
mem1 = (int*) malloc(size*sizeof(int)); 
        puts("\n[Allocated first chunk]"); 
        puts_rusage(); 
for(i=0; i 
mem1[i]=i; 
} 
        puts("\n[Populated first chunk]"); 
        puts_rusage(); 
        mem2 = (int*) malloc(size*sizeof(int)); 
        puts("\n[Allocated second chunk]"); 
        puts_rusage(); 
for(i=0; i 
mem2[i]=i; 
} 
        puts("\n[Populated second chunk]"); 
        puts_rusage(); 
mem3 = (int*) malloc(size*sizeof(int)); 
        puts("\n[Allocated third chunk]"); 
        puts_rusage(); 
for(i=0; i 
mem3[i]=i; 
} 
        puts("\n[Populated third chunk]"); 
        puts_rusage(); 
mem4 = (int*) malloc(size*sizeof(int)); 
        puts("\n[Allocated fourth chunk]"); 
        puts_rusage(); 
for(i=0; i 
mem4[i]=i; 
} 
        puts("\n[Populated fourth chunk]"); 
        puts_rusage(); 
free(mem1); 
        puts("\n\n* Freed first chunk."); 
free(mem2); 
        puts("* Freed second chunk."); 
free(mem3); 
        puts("* Freed third chunk."); 
free(mem4); 
        puts("* Freed fourth chunk."); 
        puts_rusage(); 
return 0; 
} 
The last test should be throwing different processes that allocate a quite large chunk of memory and see how they slow the system (if they do -- I suppose if you don't keep them doing something, they will be paged out).

Conclusion

Definitely I think there is something is not in order with the memory management. The scheduler seems ok. The same tests left the PowerBook usable, while the iMac wasn't (however it took significantly less time in almost every task).

Saturday, April 1, 2006

A volte gli umani ancora...

Ci sono alcuni tipi di ottimizzazione che per un umano sono "evidenti", per una macchina no. Trovo molto interessanti i problemi nel campo della correttezza (ovvero cercatr di insegnare ad un computer a dimostrare se un sorgente è o meno corretto, se presenta certi errori, in generale capire cosa fa). Il problema gemello è quello dell'ottimizzazione (si tratta per il computer di capire cosa fa il tuo codice e di modificarlo in uno equivalente più veloce)
Per esempio prendiamo questa funzione:
int func(){
    int i;
    int x =  2<<10;
    for ( i=0; i < MAX; ++i){
        if (i>= 0 &&  sqrt(i) >= 0)
            x/=i;
    }
}
Ad occhio si vede benissimo che il check dell'if è oltremodo pesante. *sai* che i è sempre maggiore o uguale di 0. Si può anche farne una dimostrazione formale abbastanza agevole.
In pratica la guardia dell'if è inutile. Il check sul >= 0 non serve e meno ancora sqrt. Nessuno dei due ha effetti collaterali (per il primo si vede, è facile, ma per il secondo bisogna sapere come è fatta sqrt, a sboccio non si modo di sapere che non setta un globale ad i, che stampa qualcosa o che ha un altro effetto collaterale, per cui effettivamente non si può semplicemente eliminarla senza cambiare la semantica del programma.
Dicevo. Senza ottimizzare, questo compila tenendo tutta la guardia dell'if:
L3:
cmpl    $0, -16(%ebp)
js      L4
cvtsi2sd        -16(%ebp), %xmm0
sqrtsd  %xmm0, %xmm0
movapd  %xmm0, %xmm1
leal    LC0-"L00000000001$pb"(%ebx), %eax
movsd   (%eax), %xmm0
ucomisd %xmm0, %xmm1
jae     L7
jmp     L4

C'è il primo confronto i>= 0
cmpl    $0, -16(%ebp)
js      L4


e c'è pure il confronto con la radice (sta usando dei registri mmx).
Bene... tutta la sezione L3 in effetti si può semplicemente togliere. Ora in questo caso è semplicemente banale fare l'ottimizzazione. E in effetti tutto il codice completo per la funzione di cui sopra ottimizzato è:
.text
.globl _func
_func:
pushl   %ebp
movl    %esp, %ebp
xorl    %eax, %eax
L2:
addl    $1, %eax
cmpl    $10, %eax
jne     L2
popl    %ebp
ret
.subsections_via_symbols
Lungo da solo quanto il controllo. E questo è quasi esattamente quello che avrebbe scritto un programmatore:
Piccolo preludio, azzera il primo registro. Poi nel loop, incrementa il primo registro (addl $1, %eax), confrontalo con il valore guardia (nel sorgente MAX era una define a 10 ; cmpl $10, %eax), se è minore o uguale torna a L2 (jne L2). Esci.
Ha ottimizzato perfino x/=i. Siccome vede che con x non ci faccio nulla, allora dice: che lo calcolo a fare? Fa solo il ciclo. Fosse stato più furbo non avrebbe fatto manco quello. Stupido io a prendere l'esempio fatto male.
Modifichiamo quindi la funzione in modo che ritorni x, e che quindi x vada calcolato.
Ecco... vediamo che a questo punto non è più tanto furbo:
.text
.globl _func
_func:
pushl   %ebp
movl    %esp, %ebp
pushl   %ebx
xorl    %ecx, %ecx
movl    $2048, %eax
pxor    %xmm1, %xmm1
jmp     L2
L3:
testl   %ecx, %ecx
js      L11
L2:
cvtsi2sd        %ecx, %xmm0
sqrtsd  %xmm0, %xmm0
ucomisd %xmm1, %xmm0
jb      L11
cltd
idivl   %ecx
L11:
addl    $1, %ecx
cmpl    $9, %ecx
jle     L3
popl    %ebx
popl    %ebp
ret
.subsections_via_symbols

Ricompare la radice quadrata ( sqrtsd %xmm0, %xmm0 ). Il programmatore che avesse scritto l'assembly a mano avrebbe scritto [ nel caso in cui questo loop sia molto ricorrente ] un codice significativamente più veloce.
Ammesso che questo mio esempio è del tutto cretino, è vero che il compilatore in genere sa su quale architettura certe istruzioni sono più sgamate, ma è vero ancora che le tecniche per le dimostrazioni formali sono ancora relativamente poco usate (anche perchè suddette dimostrazioni dilatano di moltissimo il tempo di compilazione, sono *molto* difficili da scrivere, e rischiano di portare bachi su bachi con errori minimi). Questo è parte di quasi tutti gli ambienti, non solo del gcc.
Come dire... l'umano sulle cose "furbe" resta più furbo, anche se sulla forza bruta non ha speranza.