]>
mj.ucw.cz Git - libucw.git/log
Pavel Charvat [Wed, 26 Sep 2007 06:53:43 +0000 (08:53 +0200)]
Fixed a bug in fixint sorter.
Pavel Charvat [Fri, 21 Sep 2007 14:13:25 +0000 (16:13 +0200)]
Merge with git+ssh://git.ucw.cz/projects/sherlock/GIT/sherlock.git
Martin Mares [Fri, 21 Sep 2007 10:10:30 +0000 (12:10 +0200)]
Fixed a typo.
Martin Mares [Fri, 21 Sep 2007 09:15:56 +0000 (11:15 +0200)]
The graph tests are able to generate empty input now.
Pavel Charvat [Fri, 21 Sep 2007 09:15:46 +0000 (11:15 +0200)]
Merge with git+ssh://git.ucw.cz/projects/sherlock/GIT/sherlock.git
Martin Mares [Fri, 21 Sep 2007 09:14:55 +0000 (11:14 +0200)]
Do not die on ASSERT when sorting an empty input with custom presorter.
We have test that not only the join bucket is available, but that the join
has actually happened, because custom presorters do not implement automatic
joining.
Pavel Charvat [Fri, 21 Sep 2007 07:43:46 +0000 (09:43 +0200)]
Merge with git+ssh://git.ucw.cz/projects/sherlock/GIT/sherlock.git
Martin Mares [Thu, 20 Sep 2007 17:48:30 +0000 (19:48 +0200)]
Added a very brief introduction to ASIO.
Martin Mares [Thu, 20 Sep 2007 17:32:21 +0000 (19:32 +0200)]
Added copyright messages.
Martin Mares [Thu, 20 Sep 2007 17:01:37 +0000 (19:01 +0200)]
Documented the changes in dev-sorter.
Martin Mares [Thu, 20 Sep 2007 16:14:54 +0000 (18:14 +0200)]
Polished the introductory comments in sorter.h.
Martin Mares [Wed, 19 Sep 2007 21:41:07 +0000 (23:41 +0200)]
Fix the swapping bug, this time correctly.
Martin Mares [Wed, 19 Sep 2007 21:18:27 +0000 (23:18 +0200)]
Merge with git+ssh://git.ucw.cz/projects/sherlock/GIT/sherlock.git#dev-sorter
Martin Mares [Wed, 19 Sep 2007 21:18:10 +0000 (23:18 +0200)]
Fixed a bug in s-internal, which caused it to write bogus records
when the array sorter decided to swap buffers.
Martin Mares [Mon, 17 Sep 2007 20:06:05 +0000 (22:06 +0200)]
Honor SORT_DEBUG_KEEP_BUCKETS when swapping in a bucket.
Martin Mares [Mon, 17 Sep 2007 20:04:17 +0000 (22:04 +0200)]
Print item counts as %u's.
Martin Mares [Mon, 17 Sep 2007 19:39:02 +0000 (21:39 +0200)]
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.
Martin Mares [Mon, 17 Sep 2007 19:28:31 +0000 (21:28 +0200)]
Removed a reference to the old sorter.
Martin Mares [Sun, 16 Sep 2007 20:30:52 +0000 (22:30 +0200)]
Added another note.
Martin Mares [Sun, 16 Sep 2007 20:16:34 +0000 (22:16 +0200)]
Merge with git+ssh://git.ucw.cz/projects/sherlock/GIT/sherlock.git#dev-sorter
Martin Mares [Sun, 16 Sep 2007 20:16:21 +0000 (22:16 +0200)]
Fixed a silly bug in the parallel radix-sorter.
Pavel Charvat [Fri, 14 Sep 2007 07:21:01 +0000 (09:21 +0200)]
fixed a memory leak
Pavel Charvat [Fri, 14 Sep 2007 07:16:42 +0000 (09:16 +0200)]
removed a traling whitespace
Martin Mares [Tue, 11 Sep 2007 17:00:43 +0000 (19:00 +0200)]
Fixed a nasty bug in the threaded radix-sorter.
Martin Mares [Tue, 11 Sep 2007 16:59:42 +0000 (18:59 +0200)]
Use large thread stack.
Martin Mares [Tue, 11 Sep 2007 16:59:29 +0000 (18:59 +0200)]
Adjust thread stack size according to radix sorter parameters.
Martin Mares [Tue, 11 Sep 2007 16:26:03 +0000 (18:26 +0200)]
Cleaned up tracing levels. Array sorter now has its own control knob.
Martin Mares [Tue, 11 Sep 2007 16:01:48 +0000 (18:01 +0200)]
Use a different file access method for small inputs.
Martin Mares [Tue, 11 Sep 2007 15:49:19 +0000 (17:49 +0200)]
Made terminology of the parallel radix-sort consistent with the sequential one.
Martin Mares [Tue, 11 Sep 2007 14:04:04 +0000 (16:04 +0200)]
Intelligent switching of radix-sort buffers.
Martin Mares [Tue, 11 Sep 2007 13:38:24 +0000 (15:38 +0200)]
Do not make retros by default, since it does not compile on all CPU's
(it uses SSE intrinsics).
Martin Mares [Tue, 11 Sep 2007 13:26:48 +0000 (15:26 +0200)]
Auto-tune radix-sort width according to CPU type.
Martin Mares [Tue, 11 Sep 2007 13:17:38 +0000 (15:17 +0200)]
Sweeping over TODO.
Martin Mares [Tue, 11 Sep 2007 12:49:31 +0000 (14:49 +0200)]
Another minor optimization: Added AddRadixBits.
Martin Mares [Tue, 11 Sep 2007 12:07:42 +0000 (14:07 +0200)]
Yet another sorter tuning utility.
Martin Mares [Mon, 10 Sep 2007 19:00:35 +0000 (21:00 +0200)]
Oops, some typos have crept in.
Martin Mares [Mon, 10 Sep 2007 18:55:23 +0000 (20:55 +0200)]
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.
Martin Mares [Mon, 10 Sep 2007 18:05:10 +0000 (20:05 +0200)]
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.
Martin Mares [Mon, 10 Sep 2007 18:03:27 +0000 (20:03 +0200)]
Let eltpools maintain the number of allocated items. The overhead
is minimal and it helps debugging.
Martin Mares [Mon, 10 Sep 2007 17:47:03 +0000 (19:47 +0200)]
Implemented ThreadChunk limit.
Martin Mares [Mon, 10 Sep 2007 17:31:00 +0000 (19:31 +0200)]
Made radix-sorting threshold configurable and let radix-tune-bits
help find the optimum.
Martin Mares [Mon, 10 Sep 2007 15:18:52 +0000 (17:18 +0200)]
Fixed several bugs in swapping of buffers in the threaded radix-sorter,
which caused it to malfunction with some bit widths.
Martin Mares [Mon, 10 Sep 2007 15:18:02 +0000 (17:18 +0200)]
Added a simple utility for tuning the radix-sorter width.
Martin Mares [Mon, 10 Sep 2007 15:17:38 +0000 (17:17 +0200)]
A subset of tests can be requested now. Also, the radix sort width
can be overridden by making with `CEXTRA="-DFORCE_RADIX_BITS=n"'.
Martin Mares [Mon, 10 Sep 2007 15:16:39 +0000 (17:16 +0200)]
Radix sort bit width is now controlled by the configure script.
Martin Mares [Mon, 10 Sep 2007 15:14:50 +0000 (17:14 +0200)]
Fixed a typo in usage text.
Martin Mares [Mon, 10 Sep 2007 15:14:24 +0000 (17:14 +0200)]
Added CEXTRA and LEXTRA, which can be used to add new compilation/linking
flags without removing the original ones.
Martin Mares [Mon, 10 Sep 2007 11:40:44 +0000 (13:40 +0200)]
We want to keep the results of retros benchmarking, but the rest of BENCH
is obsolete.
Martin Mares [Mon, 10 Sep 2007 11:38:43 +0000 (13:38 +0200)]
Slightly improved user interface of {asio,file}-test and renamed them
to radix-*.
Martin Mares [Sat, 8 Sep 2007 20:53:46 +0000 (22:53 +0200)]
Removed sorter_presort_bufsize, it was no longer used.
Martin Mares [Sat, 8 Sep 2007 20:49:54 +0000 (22:49 +0200)]
Clean up #undef's.
Martin Mares [Sat, 8 Sep 2007 20:40:29 +0000 (22:40 +0200)]
Explain why we don't need the join hack for custom presorting.
Martin Mares [Sat, 8 Sep 2007 18:25:00 +0000 (20:25 +0200)]
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.
Martin Mares [Sat, 8 Sep 2007 17:51:30 +0000 (19:51 +0200)]
Changed the interface of the array sorter: the buffer and hash_bits parameters
are passed only if hashing is enabled.
Martin Mares [Sat, 8 Sep 2007 14:35:50 +0000 (16:35 +0200)]
Moved the last few relevant NOTES to TODO.
Martin Mares [Sat, 8 Sep 2007 14:28:23 +0000 (16:28 +0200)]
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.
Martin Mares [Sat, 8 Sep 2007 14:20:16 +0000 (16:20 +0200)]
The old sorter is gone.
Martin Mares [Sat, 8 Sep 2007 14:07:59 +0000 (16:07 +0200)]
Cleanup FIXME's.
Martin Mares [Fri, 7 Sep 2007 17:15:36 +0000 (19:15 +0200)]
Shaved off a couple of items from the TODO.
Martin Mares [Fri, 7 Sep 2007 17:03:04 +0000 (19:03 +0200)]
Both quicksort and radix-sort can be parallelized to multiple threads now.
Martin Mares [Fri, 7 Sep 2007 14:45:50 +0000 (16:45 +0200)]
Improved heuristics for internal sorter capacity estimation.
Martin Mares [Fri, 7 Sep 2007 13:55:47 +0000 (15:55 +0200)]
A few improvements of sort-test.
Martin Mares [Fri, 7 Sep 2007 13:34:05 +0000 (15:34 +0200)]
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).
Martin Mares [Fri, 7 Sep 2007 12:33:55 +0000 (14:33 +0200)]
Merge with git+ssh://cvs.ucw.cz/projects/sherlock/GIT/sherlock.git#dev-sorter
Martin Mares [Fri, 7 Sep 2007 12:33:45 +0000 (14:33 +0200)]
Added basic threading parameters.
Martin Mares [Fri, 7 Sep 2007 12:33:26 +0000 (14:33 +0200)]
Merge with git+ssh://git.ucw.cz/projects/sherlock/GIT/sherlock.git#dev-sorter
Martin Mares [Fri, 7 Sep 2007 12:31:37 +0000 (14:31 +0200)]
Added a debugging hack.
Martin Mares [Fri, 7 Sep 2007 12:29:34 +0000 (14:29 +0200)]
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.
Martin Mares [Fri, 7 Sep 2007 12:27:29 +0000 (14:27 +0200)]
Added numbering of tests.
Martin Mares [Fri, 7 Sep 2007 10:30:18 +0000 (12:30 +0200)]
Cleanup of array sorter interface and added quicksplit.
Martin Mares [Thu, 6 Sep 2007 20:00:10 +0000 (22:00 +0200)]
A few bits of commentary.
Martin Mares [Thu, 6 Sep 2007 19:27:31 +0000 (21:27 +0200)]
More bits of the array sorter: radix-sort implemented.
Martin Mares [Thu, 6 Sep 2007 19:26:49 +0000 (21:26 +0200)]
Fixed multi-way sorting with custom presorting.
Martin Mares [Thu, 6 Sep 2007 15:16:10 +0000 (17:16 +0200)]
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.
Martin Mares [Thu, 6 Sep 2007 14:17:42 +0000 (16:17 +0200)]
Added a simple allocator for fixed-size objects.
Pavel Charvat [Thu, 6 Sep 2007 07:19:33 +0000 (09:19 +0200)]
Merge with git+ssh://git.ucw.cz/projects/sherlock/GIT/sherlock.git
Martin Mares [Wed, 5 Sep 2007 18:14:08 +0000 (20:14 +0200)]
Unified top-level Makefile with main-line.
Martin Mares [Wed, 5 Sep 2007 18:10:16 +0000 (20:10 +0200)]
We don't need this as 2-way merging is used rarely.
Pavel Charvat [Tue, 4 Sep 2007 21:21:29 +0000 (23:21 +0200)]
library: bugfix in SH_CONFIG
Pavel Charvat [Tue, 4 Sep 2007 19:49:49 +0000 (21:49 +0200)]
library:
the environment variable with configuration file is now user-defined
(SH_CONFIG by default)
Pavel Charvat [Tue, 4 Sep 2007 19:22:20 +0000 (21:22 +0200)]
library:
SH_CONFIG environment variable can override the default configuration file
Pavel Charvat [Tue, 4 Sep 2007 16:42:04 +0000 (18:42 +0200)]
bugfix in the installer
Martin Mares [Fri, 31 Aug 2007 19:07:15 +0000 (21:07 +0200)]
New TODO notes.
Martin Mares [Fri, 31 Aug 2007 14:08:26 +0000 (16:08 +0200)]
A couple of things done.
Martin Mares [Fri, 31 Aug 2007 13:45:28 +0000 (15:45 +0200)]
Join in the rare case that presorting creates a single run, which is
not known in advance to be final.
Martin Mares [Fri, 31 Aug 2007 13:37:02 +0000 (15:37 +0200)]
Cleaned up joining logic and implemented joins in multi-way merges.
Martin Mares [Fri, 31 Aug 2007 12:57:49 +0000 (14:57 +0200)]
Added decision logic which switches between 2-way merges, n-way merges
and radix splits.
Martin Mares [Fri, 31 Aug 2007 11:42:50 +0000 (13:42 +0200)]
Merge with git+ssh://git.ucw.cz/projects/sherlock/GIT/sherlock.git#dev-sorter
Martin Mares [Fri, 31 Aug 2007 11:42:43 +0000 (13:42 +0200)]
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.
Pavel Charvat [Fri, 31 Aug 2007 11:09:11 +0000 (13:09 +0200)]
Merge with git+ssh://git.ucw.cz/projects/sherlock/GIT/sherlock.git
Martin Mares [Fri, 31 Aug 2007 09:47:12 +0000 (11:47 +0200)]
Merge with git+ssh://git.ucw.cz/projects/sherlock/GIT/sherlock.git#dev-sorter
Martin Mares [Fri, 31 Aug 2007 09:46:44 +0000 (11:46 +0200)]
Better (and correct) handling of joins and empty buckets.
Martin Mares [Thu, 30 Aug 2007 09:58:00 +0000 (11:58 +0200)]
Cleanup and commentary.
Martin Mares [Thu, 30 Aug 2007 09:48:57 +0000 (11:48 +0200)]
Added a work-around for nasty GCC bug.
Martin Mares [Thu, 30 Aug 2007 09:37:14 +0000 (11:37 +0200)]
Yet another swap-out.
Martin Mares [Thu, 30 Aug 2007 08:00:35 +0000 (10:00 +0200)]
Fixed the yesterday's mysterious bug.
Martin Mares [Thu, 30 Aug 2007 08:00:20 +0000 (10:00 +0200)]
Presorting for multi-way merge should swap out the buckets.
Martin Mares [Wed, 29 Aug 2007 21:10:30 +0000 (23:10 +0200)]
So far buggy support for multi-way unification.
Martin Mares [Wed, 29 Aug 2007 21:10:13 +0000 (23:10 +0200)]
Fixed bug in error message.
Martin Mares [Wed, 29 Aug 2007 21:09:52 +0000 (23:09 +0200)]
Merge with git+ssh://cvs.ucw.cz/projects/sherlock/GIT/sherlock.git#dev-sorter