Print item counts as %u's.

Array sorter thresholds are now configured as 64-bit numbers of bytes,
but they are recalculated to the number of elements internally with
proper clamping to ~0U.

Removed a reference to the old sorter.

Added another note.

Merge with git+ssh://git.ucw.cz/projects/sherlock/GIT/sherlock.git#dev-sorter

Fixed a silly bug in the parallel radix-sorter.

fixed a memory leak

removed a traling whitespace

Fixed a nasty bug in the threaded radix-sorter.

Use large thread stack.

Adjust thread stack size according to radix sorter parameters.

Cleaned up tracing levels. Array sorter now has its own control knob.

Use a different file access method for small inputs.

Made terminology of the parallel radix-sort consistent with the sequential one.

Intelligent switching of radix-sort buffers.

Do not make retros by default, since it does not compile on all CPU's
(it uses SSE intrinsics).

Auto-tune radix-sort width according to CPU type.

Sweeping over TODO.

Another minor optimization: Added AddRadixBits.

Yet another sorter tuning utility.

Oops, some typos have crept in.

Redefined RadixThreshold to bound the array size instead of the number
of elements -- the switching point seems to be related more to cache
effects than decision performance.

Rewritten handling of small chunks in the parallel radix-sorter.

They are now immediately submitted to the worker thread instead of keeping
them in a list of delayed chunks for the whole course of the algorithm.
This avoids memory usage explosions caused by queueing lots of smallish
chunks. We prefer to wait for the small chunks to complete before starting
the next large chunk.

Let eltpools maintain the number of allocated items. The overhead
is minimal and it helps debugging.

Implemented ThreadChunk limit.

Made radix-sorting threshold configurable and let radix-tune-bits
help find the optimum.

Fixed several bugs in swapping of buffers in the threaded radix-sorter,
which caused it to malfunction with some bit widths.

Added a simple utility for tuning the radix-sorter width.

A subset of tests can be requested now. Also, the radix sort width
can be overridden by making with `CEXTRA="-DFORCE_RADIX_BITS=n"'.

Radix sort bit width is now controlled by the configure script.

Fixed a typo in usage text.

Added CEXTRA and LEXTRA, which can be used to add new compilation/linking
flags without removing the original ones.

We want to keep the results of retros benchmarking, but the rest of BENCH
is obsolete.

Slightly improved user interface of {asio,file}-test and renamed them
to radix-*.

Removed sorter_presort_bufsize, it was no longer used.

Clean up #undef's.

Explain why we don't need the join hack for custom presorting.

Convert the most important users of arraysort.h to sorter/array.h.

So far, I didn't have used radix-sorting, because I want to save memory,
but if any of these sorters will turn up on the profiles, I will convert it
later.

Changed the interface of the array sorter: the buffer and hash_bits parameters
are passed only if hashing is enabled.

Moved the last few relevant NOTES to TODO.

Install API of the new sorter.

I had to get rid of the $(?F) construct, because did not work with includes
in subdirectories (like sorter has). I have replaced it by a direct reference
to the include list macro, which also allows to add the missing dependency
on autoconf.h.

The old sorter is gone.

Cleanup FIXME's.

Shaved off a couple of items from the TODO.

Both quicksort and radix-sort can be parallelized to multiple threads now.

Improved heuristics for internal sorter capacity estimation.

A few improvements of sort-test.

Save cache misses by keeping a copy of the hash value next to the pointer.

This trades cache efficiency for extra memory, but it seems to be very well
worth it (e.g., graph sorting in sort-test is 8 times faster now).

Merge with git+ssh://cvs.ucw.cz/projects/sherlock/GIT/sherlock.git#dev-sorter

Added basic threading parameters.

Merge with git+ssh://git.ucw.cz/projects/sherlock/GIT/sherlock.git#dev-sorter

Added a debugging hack.

Introduced ARRAY_LONG_HASH and unrolled radix-sorting primitives.

Also tuned ASORT_RADIX_BITS for P4 Xeon (Sherlock3) -- the L1 cache is
so small there that it is better to tune radix-sort for L2 cache size.

Added numbering of tests.

Cleanup of array sorter interface and added quicksplit.

A few bits of commentary.

More bits of the array sorter: radix-sort implemented.

Fixed multi-way sorting with custom presorting.

Added a sketch of a new array sorter implementation.

The interface is already hopefully fixed, I am going to add the missing bits
of implementation soon.

Added a simple allocator for fixed-size objects.

Merge with git+ssh://git.ucw.cz/projects/sherlock/GIT/sherlock.git

Unified top-level Makefile with main-line.

We don't need this as 2-way merging is used rarely.

bugfix in the installer

New TODO notes.

A couple of things done.

Join in the rare case that presorting creates a single run, which is
not known in advance to be final.

Cleaned up joining logic and implemented joins in multi-way merges.

Added decision logic which switches between 2-way merges, n-way merges
and radix splits.

Merge with git+ssh://git.ucw.cz/projects/sherlock/GIT/sherlock.git#dev-sorter

The GCC bug (I hope I have ruled out all possibilities of a bug at my side)
turned out to bite even in GCC 4.2.1, so I have reported it and enabled
the workaround for all compiler versions.

Merge with git+ssh://git.ucw.cz/projects/sherlock/GIT/sherlock.git

Merge with git+ssh://git.ucw.cz/projects/sherlock/GIT/sherlock.git#dev-sorter

Better (and correct) handling of joins and empty buckets.

Cleanup and commentary.

Added a work-around for nasty GCC bug.

Yet another swap-out.

Fixed the yesterday's mysterious bug.

Presorting for multi-way merge should swap out the buckets.

So far buggy support for multi-way unification.

Fixed bug in error message.

Merge with git+ssh://cvs.ucw.cz/projects/sherlock/GIT/sherlock.git#dev-sorter

Fixed a bug.

Added options for gcc 4.2.x.

Bugfix in keywords module -- fb-dir does not support appending to an
unaligned file.

format_size() no longer exists.

Multi-way merges work fine in simple cases.
I am going to give them a try on large data to see if they are viable.

Setting of LIBS is no longer necessary.

Updated TODO.

Dependencies of test programs are no longer hard-wired in the rules.

Cosmetics.

Shared file handles now use is_temp_file == 2 instead of -1
to avoid collisions with negative return values of bconfig()
meaning "not supported".

Cleanup of file fastbufs.

  o  Common parts of close code moved to bclose_file_helper().
  o  Compatibility wrappers moved to fb-param.c.
  o  Everything related to temp files moved to fb-temp.c.
  o  Several byte -> char conversions.
  o  Better comments.
  o  Testing code compiles again.

bopen_tmp_file(NULL) works.

Use bfix_tmp_file() whereever possible.

Implemented bfix_tmp_file(), which turns a temporary file fastbuf
to a permanent one.

Let bconfig() return the original value.

Removed obsolete comment.

Fixed a typo.

LIBUCW needs to be declared early, because it is used by sub-Makefiles.