Oleg Zabluda's blog
Wednesday, April 25, 2012
 
Academic research on sorting algorithms typically assumes either random initial conditions (average complexity) or...
Academic research on sorting algorithms typically assumes either random initial conditions (average complexity) or worst case conditions. However in real world, the sequence is almost always non-random and have large ascending or descending sub-sequences. Worst case can happen if it is common (i.e. reverse order for quicksort) or due to DOS via Algorithmic Complexity Attack. Which brings us to

http://en.wikipedia.org/wiki/Timsort

"""
Timsort is a hybrid sorting algorithm, derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data. It was invented by Tim Peters in 2002 for use in the Python programming language. The algorithm finds subsets of the data that are already ordered, and uses the subsets to sort the data more efficiently. [...] Timsort has been Python's standard sorting algorithm since version 2.3. It is now also used to sort arrays in Java SE 7, and on the Android platform.
"""

Timsort has best case complexity of N, at the cost of requiring additional memory, as much as N/2 pointers for the random data.

References:
http://mail.python.org/pipermail/python-dev/2002-July/026837.html
http://svn.python.org/projects/python/trunk/Objects/listsort.txt
http://www.drmaciver.com/2010/01/understanding-timsort-1adaptive-mergesort/
http://en.wikipedia.org/wiki/Sorting_algorithm
http://en.wikipedia.org/wiki/Timsort

Labels:


- posted by Oleg Zabluda @ 6:11 PM | permalink | | | technorati | bloglines | feedster
 
Double-checked locking pattern (http://en.wikipedia.org/wiki/Double-checked_locking), was first published by Douglas...
Double-checked locking pattern (http://en.wikipedia.org/wiki/Double-checked_locking), was first published by Douglas C. Schmidt, Editor-in-chief C++ Report, in March 1996
http://www.cs.wustl.edu/~schmidt/editorial-3.html

That double-checked locking implementation was still considered correct in Oct 1999 Dr. Dobbs Journal (DDJ) article "Singleton Creation the Thread-safe Way".
http://www.drdobbs.com/article/print?articleId=184403715

The first time people started realizing that the canonical implementation is actually wrong, was around 2001.
http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html

By 2004, there was a good comprehensive article about it:
Scott Meyers and Andrei Alexandrescu September 2004 DDJ paper:
"C++ and the Perils of Double-Checked Locking"
http://www.aristeia.com/Papers/DDJ_Jul_Aug_2004_revised.pdf

At the time, it was quite instructive to me to see how that could have slipped by so many experts for so long, and how long it took people to figure out what is trivial now:

One thread writes to variable with the lock held, but another thread reads same variable without lock held. It's a data race, plane and simple.

The reason it is so trivial now is due to heroic efforts of many people, the most by Hans Boehm, who not only figured it out, but formalized C/C++ memory model and contributed to Java memory model. He also provides the best currently known implementation on the last slide of his, from his recent ACM Bay Area talk

http://www.hpl.hp.com/personal/Hans_Boehm/misc_slides/sfacm-cleaned.pdf

C++11 fine-tuned double-checked locking

atomic x_init;
if (!x_init.load(memory_order_acquire) {
l.lock();
if (!x_init.load(memory_order_relaxed) {
initialize x;
x_init.store(true, memory_order_release);
}
l.unlock();
}
use x;

Intel/AMD finally published their official memory models in 2007-2008.
Turns out on x86 the implementation above is "free" i.e. requires no additional fences, locks or nothing.
http://www.justsoftwaresolutions.co.uk/threading/intel-memory-ordering-and-c++-memory-model.html

Also see:
https://plus.google.com/112065430692128821190/posts/EjTBDUuS38G
http://www.hpl.hp.com/personal/Hans_Boehm/misc_slides/sfacm-cleaned.pdf

Labels:


- posted by Oleg Zabluda @ 2:02 PM | permalink | | | technorati | bloglines | feedster

Powered by Blogger