Re: fast stable sort

From: CBFalconer <cbfalco...@xxxxxxxxx>
How do you load a herd of (variable length) strings into your
system without at least an auxiliary table of pointers to the
individual strings?

For fastest load, at expense of slower sort, you ask the operating
system the size of the file, you allocate an array of exactly that
size rounded up to exact multiple of page size and aligned on page
boundary, and you memory-map the file directly into that array.
Whatever was the delimiter in the file serves also as delimiter in
VM/RAM-array verbatim-copy of the file.

To achieve faster sort, at expense of slower load, you parse each
record from disk into adjustable array or linked list or
linked-chunks or any other data structure you like which will
support loading a record of unknown size, then as soon as you reach
the terminal delimiter you copy all the data of the record,
preceded by a single word telling its length, into next available
memory of your big array. If the new record won't fit in the array,
resize it bigger.

Once you recognize this, the obvious way to load the strings is
with a singly linked list.

Maybe, maybe not. You still have to parse incoming record into some
temporary expandable data structure prior to copying it all to
where it will finally reside. If you're not careful, you will be
allocating consecutive records scattered all over virtual address
space, so that later when you try to merge sort your memory
accesses will be non-local causing swapping to thrash. If your heap
allocation system allows you to deal with multiple contiguous
blocks of address space, and it provides a way to pack data from
one block into another block to make it all consecutive, then it's
possible to assure locality of reference and thus avoid thrashing
if you are careful to do a deep copy of all your records into a new
block of consecutive memory with each merge pass. But if you fail
to move the data to new consecutive locations with each merge pass,
then even though your linked-list of pointers to records gets moved
to consecutive memory with each merge pass, the actual data records
will sit put and access to them will become increasingly random
causing thrashing.

I don't know of any Lisp system that gives you such control over
multiple heap blocks that you can maintain locality of reference
within merge runs. I don't know enough about what's available in
other languages, such as C, to say anything at all about what's
available like that.

Note that the sort only diddles the pointers, not the strings.

That stupid idea virtualy guarantees non-locality of reference
towards the end of sorting data that was originally pseudo-random
with respect to the key being sorted, thus assuring thrashing if
the entire heap won't fit in physical RAM.