4
\$\begingroup\$

I have been working on sorting a file in-place with heapsort. I'm very glad it is working. But the time it takes is just too much. So I was wondering on how I could improve it.

Here are my requirements:

  • The file consists of 14B index entries. One index entry consists of 8B of the actual index and 6B of offset. I want to sort these entries after the first 8B. The remaining 6B will need to be dragged along but will not be required for sorting.
  • The sorting has to occur in-place. No additional files may be created
  • I need to able to tell the progress. I display a progress bar of the sorting while it runs.
  • Some amount of RAM may be used to speed up sorting. The amount will be passed as a parameter
  • You can parallize the sorting. But if you do there will be a limit of threads you can create which would also be passed in a parameter if you need it.
  • The sorting does not need to be stable.
  • You may use a different sorting algorithm

Before I show you my current code I want to add a few notes:
The reason I chose Heapsort over Quicksort is the fact that I want to have a progress bar. I ask you not to debate this requirement.
The files may be a lot larger than the available RAM. That's why you can't load the file entierly into RAM.
The first 8B of each entry are pretty much random and evenly distributed.
My current aproach constits of loading the first index entries into RAM until I reach the limit. And writing that data into the file after the sorting finishes.
Should you find any other issues like bad code style feel free to correct me too.
I use CSI escape sequences to display the progress bar. If you are not familiar with it just leave the code as it is. It is working as intended anyway and I just included it for the sake of completeness.

sortidx.h

#ifndef SORTIDX_H
#define SORTIDX_H

// Includes
#include <algorithm>
#include <atomic>
#include <fstream>
#include <iostream>
#include <limits>
#include <string>
#include <thread>

#include "util.h"

// Functions
// Returns the parent index.
constexpr size_t getParent( size_t i ) {
    return (i - 1) / 2;
}

// Returns the left child index.
constexpr size_t getLeft( size_t i ) {
    return i * 2 + 1;
}

// Returns the right child index.
constexpr size_t getRight( size_t i ) {
    return i * 2 + 2;
}

// Sorts an idx file. Using chachSize bytes of RAM to speed it up.
void sortIDX( std::string idxFile, size_t cacheSize, bool quiet );

// Reads the specified number of elements into the cache
void readIntoCache( size_t numElements );
// Writes the cache to the file
void writeFromCache();

// Turns the idx file into a heap (first step of heapsort)
void heapifyIDX( size_t heapifyLimit );
// Sorts the idx heap (second step of heapsort)
void sortIDXHeap( size_t numDataSets );

// Reads data at the specified location. Either from cache or from disk.
void readData( IndexEntry* entry, size_t pos );
// Writes data at the specified location. Either to cache or to disk.
void writeData( IndexEntry* entry, size_t pos );
// Checks whether a index is in the heap
bool isInHeap( size_t pos );
// Moves a element down the heap until it is at the right position
void orderHeap( IndexEntry &top, size_t posTop );

#endif

sortidx.cpp

#include "sortidx.h"

using namespace std;

streampos fileSize;
size_t numDataSets;
size_t limit;
atomic<size_t> pos;
fstream* file;
size_t arraySize = 0;
IndexEntry* cacheArray;

void readIntoCache( size_t numElements ) {
    if ( arraySize != 0 )
        writeFromArray();

    arraySize = numElements;
    cacheArray = new IndexEntry[arraySize];
    file->seekg( 0 );

    for ( size_t i = 0; i < arraySize; i++ ) {
        file->read( (char*)(cacheArray + i), writeSize );
    }
}

void writeFromCache() {
    file->seekp( 0 );

    for ( size_t i = 0; i < arraySize; i++ ) {
        file->write( (char*)(cacheArray + i), writeSize );
    }

    arraySize = 0;
    delete[] cacheArray;
}

void sortIDX( string idxFile, size_t cacheSize, bool quiet ) {
    file = new fstream( idxFile, ios::in | ios::out | ios::binary | ios::ate );
    fileSize = file->tellg();
    numDataSets = fileSize / writeSize;
    limit = numDataSets - 1;
    const size_t localLimit = limit;
    const size_t heapifyLimit = getParent( limit );
    thread* sorterThread;

    if ( !quiet )
        cout << "Sorting index (may take a while)...\n\33[sLoading cache from file..." << flush;

    cacheSize /= writeSize;
    readIntoCache( min(cacheSize, numDataSets) );

    sorterThread = new thread( heapifyIDX, heapifyLimit );

    if ( !quiet ) {
        cout << "\33[u";
        initProgress( heapifyLimit + localLimit, false );

        while ( pos <= heapifyLimit ) {
            this_thread::sleep_for( chrono::milliseconds( defaultTimeout ) );

            printProgress( (size_t)pos );
        }
    }

    sorterThread->join();
    delete sorterThread;

    pos = 0;
    sorterThread = new thread( sortIDXHeap, localLimit );

    if ( !quiet ) {
        while ( pos < localLimit ) {
            this_thread::sleep_for( chrono::milliseconds( defaultTimeout ) );

            printProgress( heapifyLimit + pos );
        }
    }

    sorterThread->join();
    delete sorterThread;

    if ( !quiet )
        cout << "\33[?25h\n\33[sSaving cache to file." << flush;

    writeFromCache();

    file->close();
    delete file;

    if ( !quiet )
        cout << "\33[u\33[KDone!" << endl;
}

void heapifyIDX( size_t heapifyLimit ) {
    IndexEntry top;
    size_t posTop;

    for ( pos = 0; pos <= heapifyLimit; pos++ ) {
        posTop = heapifyLimit - pos;

        readData( &top, posTop );

        orderHeap( top, posTop );
    }
}

void sortIDXHeap( size_t numDataSets ) {
    IndexEntry last;
    IndexEntry top;
    size_t posLast;
    size_t posTop;

    for ( pos = 0; pos < numDataSets; pos++ ) {
        posLast = numDataSets - pos;
        posTop = 0;
        limit = posLast - 1;

        readData( &last, posTop );
        readData( &top, posLast );
        writeData( &last, posLast );

        orderHeap( top, posTop );
    }
}

void readData( IndexEntry* entry, size_t pos ) {
    if ( pos < arraySize ) {
        *entry = cacheArray[pos];
    } else {
        file->seekg( pos * writeSize );
        file->read( (char*)entry, writeSize );
    }
}

void writeData( IndexEntry* entry, size_t pos ) {
    if ( pos < arraySize ) {
        cacheArray[pos] = *entry;
    } else {
        file->seekp( pos * writeSize );
        file->write( (char*)entry, writeSize );
    }
}

bool isInHeap( size_t pos ) {
    return pos <= limit;
}

void orderHeap( IndexEntry &top, size_t posTop ) {
    static IndexEntry left;
    static IndexEntry right;
    static size_t posLeft;
    static size_t posRight;
    static bool swapped;

    do {
        posLeft = getLeft( posTop );
        posRight = getRight( posTop );

        if ( isInHeap( posLeft ) ) {
            readData( &left, posLeft );

            if ( isInHeap( posRight ) ) {
                readData( &right, posRight );

                if ( right > left ) {
                    if ( right > top ) {
                        writeData( &right, posTop );
                        posTop = posRight;

                        swapped = true;
                    } else {
                        swapped = false;
                    }
                } else {
                    if ( left > top ) {
                        writeData( &left, posTop );
                        posTop = posLeft;

                        swapped = true;
                    } else {
                        swapped = false;
                    }
                }
            } else {
                if ( left > top ) {
                    writeData( &left, posTop );
                    posTop = posLeft;

                    swapped = true;
                } else {
                    swapped = false;
                }
            }
        } else {
            swapped = false;
        }
    } while ( swapped );

    writeData( &top, posTop );
}

util.h

#ifndef UTIL_H
#define UTIL_H

// Includes
#include <iomanip>
#include <iostream>
#include <stddef.h>
#include <sstream>
#include <string>
#include <thread>
#include <unistd.h>

#include <sys/ioctl.h>

// Constants
constexpr size_t hashSize = 8;
constexpr size_t offsetSize = 6;
constexpr size_t writeSize = hashSize + offsetSize;
constexpr long long defaultTimeout = 100;

struct IndexEntry {
    unsigned char hash[hashSize]; // First 64 bits of the hash
    unsigned char position[offsetSize]; // Position of word in dictionary (48-bit little endian integer)

    IndexEntry& operator=( const IndexEntry &copyFrom );
    bool operator>( const IndexEntry &lhs );
} __attribute__( (__packed__) );

// Functions
struct winsize getConsoleSize();
unsigned short getConsoleHeight();
unsigned short getConsoleWidth();

// Determines which byte postfix to use (0 = "B", 1 = "KiB", ...)
unsigned short getBytePower( std::streampos size );
// Returns the appropriate byte postfix
std::string getBytePowerPostfix( unsigned short power );
// Formats the size. If power is -1 it automatically detects the power
std::string getFormatedSize( std::streampos size, int power = -1 );

// Initializes the progress bar
void initProgress( std::streampos fileSize, bool withFileSize );
// Prints the progressbar
void printProgress( std::streampos currentPos );

#endif

util.cpp

#include "util.h"

using namespace std;

streampos totalFileSize;
unsigned short formatPower;
string fileSizeString;
bool renderWithFileSize;

IndexEntry& IndexEntry::operator=( const IndexEntry &copyFrom ) {
    size_t i;

    for ( i = 0; i < hashSize; i++ )
        hash[i] = copyFrom.hash[i];

    for ( i = 0; i < offsetSize; i++ )
        position[i] = copyFrom.position[i];

    return *this;
}

bool IndexEntry::operator>( const IndexEntry &lhs ) {
    for ( size_t i = 0; i < hashSize; i++ ) {
        if ( hash[i] > lhs.hash[i] )
            return true;
        else if ( hash[i] < lhs.hash[i] )
            return false;
    }

    return false;
}

struct winsize getConsoleSize() {
    struct winsize size;
    ioctl( STDOUT_FILENO, TIOCGWINSZ, &size );

    return size;
}

unsigned short getConsoleHeight() {
    return getConsoleSize().ws_row;
}

unsigned short getConsoleWidth() {
    return getConsoleSize().ws_col;
}

unsigned short getBytePower( streampos size ) {
    unsigned short power;

    for ( power = 0; size >= 1000; power++ )
        size = size >> 10;

    return power;
}

string getBytePowerPostfix( unsigned short power ) {
    static const string postfixes[] = { "  B", "KiB", "MiB", "GiB", "TiB", "PiB", "EiB", "ZiB", "YiB" };
    static constexpr size_t numPostfixes = sizeof( postfixes ) / sizeof( string );

    if ( power > numPostfixes ) {
        return string( "2^" ) + to_string( power * 10 ) + postfixes[0];
    } else {
        return postfixes[power];
    }
}

std::string getFormatedSize( std::streampos size, int power ) {
    unsigned short formatPower = (power <= -1) ? getBytePower( size ) : (unsigned short)power;

    stringstream ss;

    if ( power == 0 ) {
        ss << setw( 3 ) << size << "    ";
    } else {
        ss << setw( 7 ) << fixed << setprecision( 3 ) << double( size ) / double( 1 << (10 * power) );
    }

    ss << ' ' << getBytePowerPostfix( formatPower );

    return ss.str();
}

void initProgress( streampos fileSize, bool withFileSize ) {
    totalFileSize = fileSize;
    formatPower = getBytePower( fileSize );
    fileSizeString = getFormatedSize( fileSize, formatPower );
    renderWithFileSize = withFileSize;

    cout << "\33[?25l";
}

void printProgress( streampos currentPos ) {
    int barWidth = getConsoleWidth() - (renderWithFileSize ? 35 : 9);
    double progress = (double)currentPos / totalFileSize;

    cout << "\33[s\33[K[";
    int pos = barWidth * progress;
    for ( int i = 0; i < barWidth; ++i ) {
        if ( i < pos ) cout << '=';
        else if ( i == pos ) cout << '>';
        else cout << ' ';
    }

    cout << "] " << setw( 5 ) << fixed << setprecision( 1 ) << progress * 100.0 << '%';

    if ( renderWithFileSize )
        cout << ' ' << getFormatedSize( currentPos, formatPower ) << " / " << fileSizeString;

    cout << "\33[u" << flush;
}

Example main.cpp

#include "sortidx.h"

int main() {
    sortIDX( "indexFile.idx", 256 * 1024 * 1024, false );
}
\$\endgroup\$
  • \$\begingroup\$ Without some more documentation. I don't know where to start. How do you use this code? Can you add a main() with example usage. Currently it is just a jumbled set of functions. \$\endgroup\$ – Martin York Sep 21 '16 at 17:24
  • 1
    \$\begingroup\$ That is what I meant. Of course reading somewhere and storing that to RAM and then writing it somewhere else is ok. I'm going to add that as long as you use single variables the will not count toward the RAM limit. That exclusivley refers to caching parts of the file. I hope that makes everthing clearer. \$\endgroup\$ – BrainStone Sep 21 '16 at 17:34
  • 1
    \$\begingroup\$ You may as well add a C tag to this code. There is nothing inherently C++ about it. You will get more people reviewing it if you add the tag. I have to go now but I will review this evening and the first comment will be this is not C++ like in the slightest. \$\endgroup\$ – Martin York Sep 21 '16 at 17:34
  • 2
    \$\begingroup\$ @LokiAstari you seem to have overseen the usage of the standard library. Just saying it isn't C++ for the lack of classes is unjust. Putting any of the code into classes wouldn't make much sense imho. I generally try to avoid making classes when I will never create more than one instance or all members will be static. In other words if it does not represent something. This is rather a question about code style than about the language. \$\endgroup\$ – BrainStone Sep 21 '16 at 18:07
  • 1
    \$\begingroup\$ It's not just the lack of classes. It's the whole style of the program. C++ have evolved over the last 15 years to a very different style than C. Your style is very C centric. You use a few C++ features but in a C way. Your style is sometimes referred to as C with Classes but the style is not a modern C++ style which is much more declarative than C. I will go into detail in my review. \$\endgroup\$ – Martin York Sep 22 '16 at 0:44
3
\$\begingroup\$

Heapsort drawbacks

My review will be directed more to the algorithm chosen instead of the actual code. You've chosen to use heapsort, which allows you to easily compute a progress percentage. You also implemented a cache which lets you hold the top elements of the heap in memory. Accesses using the memory cache are much faster than accesses that need to be done on the file directly.

The problem with the current implementation is that there are far too many non-cached accesses. On each loop iteration of heapsort, you swap the first and last elements, and then do a push down operation, where the top element is swapped downwards through the heap. Once you leave the cached area at the top, you need to do file seeks and 14 byte file reads/writes for each swap. This is the very slow part of your program.

Quicksort

Consider what would happen with quicksort. With quicksort, you have a partitioning phase where you typically scan the array from the front looking for elements larger than the pivot, and scan the array from the back looking for elements smaller than the pivot, and then you swap those elements.

If you implemented quicksort, you could use two buffers where you read a large number of elements into the "front" buffer and a large number of elements into the "back" buffer. The partitioning step would then scan forward using the "front" buffer and scan backward using the "back" buffer, swapping elements as necessary. When you reached the end of either buffer, you would write the buffer contents back to the file and reload the next portion of the buffer. By doing this, you would always be operating on large chunks of the file at a time, instead of 14 bytes at a time.

The only problem for you would be to return a progress value, which would be somewhat trickier.

Radix sort

Radix sort is another possibility. There is an inplace version of radix sort called MSD in-place radix sort. Essentially, it sorts all the elements by the first byte of the key into 256 buckets, and then recursively sorts each bucket by the second byte of the key, etc, until it reaches the last byte of the key. When the buckets are small enough, it switches to some other sort (such as insertion sort or quick sort).

To do a file sorting version, you would need to use 256 buffers to do the partitioning phase where you swap the elements into their correct buckets. Although the buffers would be smaller than with quicksort, the partitioning is more efficient because each pass through the file results in a 256-way split instead of a 2-way split.

Sample implementation

I wrote my own radix sort program to see how it would fare versus the original program. It's rather long and written in C:

//
// This program does an inplace sort of a file using radixsort combined with
// quicksort.  There is a limitation on the amount of memory that may be
// used.  The file consists of 14 byte records where the first 8 bytes
// of each record is used as the sorting key.
//
// Usage: filesort filename [max memory]
//
// Defaults to 16 MB of memory.  Only works on file sizes 4 GB or lower.  If
// you need to sort a bigger file, change all the uint32_t to uint64_t.
//
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>

// The file consists of this structure.
typedef struct Element {
    uint8_t key[8];
    uint8_t data[6];
} Element;

// This fullCache is an allocation of the entire amount of memory we can use.
Element *fullCache;
uint32_t fullCacheMaxElements;

// We also split the full cache into 256 equal sized bucket caches for when we
// do the radix sort and need to operate on 256 parts of the file at once.
typedef struct BucketCache {
    uint32_t elementIndex;
    uint32_t numElements;
    Element *data;
} BucketCache;

BucketCache cache[256];
uint32_t bucketMaxElements;

/**
 * Comparison function used by qsort().
 */
static inline int Cmp(const void *p1, const void *p2)
{
    const Element *e1 = p1;
    const Element *e2 = p2;
    for (int i=0;i<8;i++) {
        int cmp = e1->key[i] - e2->key[i];
        if (cmp != 0)
            return cmp;
    }
    return 0;
}

/**
 * Reads from file into the bucket cache.
 */
void ReadCache(FILE *fp, uint32_t bucket, uint32_t elementIndex,
        uint32_t numElements)
{
    uint32_t fileOffset = elementIndex * sizeof(Element);

    if (numElements == 0) {
        cache[bucket].numElements = 0;
        return;
    }
    if (numElements > bucketMaxElements)
        numElements = bucketMaxElements;

    uint32_t length = numElements * sizeof(Element);
    fseek(fp, fileOffset, SEEK_SET);
    fread(cache[bucket].data, 1, length, fp);
    cache[bucket].elementIndex = elementIndex;
    cache[bucket].numElements  = numElements;
}

/**
 * If we reached the end of a bucket's cache, write the contents back to the
 * file and load the next part of the bucket.
 */
static inline void FlushIfLast(FILE *fp, uint32_t bucket,
        uint32_t elementIndex, uint32_t endIndex)
{
    BucketCache *c = &cache[bucket];

    if (elementIndex == c->elementIndex + c->numElements) {
        uint32_t fileOffset = c->elementIndex * sizeof(Element);
        uint32_t length     = c->numElements * sizeof(Element);
        fseek(fp, fileOffset, SEEK_SET);
        fwrite(c->data, 1, length, fp);
        ReadCache(fp, bucket, elementIndex, endIndex - elementIndex);
    }
}

/**
 * Return a pointer to an element from a bucket's cache.
 */
static inline Element *GetElement(uint32_t bucket, uint32_t elementIndex)
{
    BucketCache *c = &cache[bucket];

    return &c->data[elementIndex - c->elementIndex];
}

/**
 * Sort a portion of the file using qsort.  This function is only called if
 * the portion we want to sort fits inside of fullCache.
 */
static void qsortSegment(FILE *fp, uint32_t offset, uint32_t len)
{
    fseek(fp, offset * sizeof(Element), SEEK_SET);
    fread(fullCache, 1, len * sizeof(Element), fp);
    qsort(fullCache, len, sizeof(Element), Cmp);
    fseek(fp, offset * sizeof(Element), SEEK_SET);
    fwrite(fullCache, 1, len * sizeof(Element), fp);
}

/**
 * This is an inplace MSD radix sort, modified to sort a file instead of
 * an array.
 */
static void radixsort(FILE *fp, uint32_t start, uint32_t end, int keyIndex)
{
    uint32_t i, j;
    uint32_t last[256] = { 0 }, current[256];
    struct Element *e, *pJ;
    struct Element temp;

    // Scan through the array/file sequentially to determine the count for
    // each bucket.
    fseek(fp, start * sizeof(Element), SEEK_SET);
    for (i=start; i<end; ) {
        // Read as much as we can into the full cache buffer.
        uint32_t cacheLen = end - i;
        if (cacheLen > fullCacheMaxElements)
            cacheLen = fullCacheMaxElements;
        fread(fullCache, 1, cacheLen * sizeof(Element), fp);
        // Now scan the elements in the full cache buffer.
        for (j=0;j<cacheLen;j++)
            ++last[fullCache[j].key[keyIndex]];
        i += cacheLen;
    }

    // Using the counts in the last array, compute the first and last element
    // index for each radix, and store them in current/last.
    current[0]  = start;
    last   [0] += start;
    for (i=1; i<256; i++) {
        current[i]  = last[i-1];
        last   [i] += last[i-1];
    }

    // Read into bucket caches the starting elements of each bucket.
    for (i=0; i<256; i++)
        ReadCache(fp, i, current[i], last[i] - current[i]);

    // Now swap elements into the correct buckets.  Whenever a bucket cache
    // fills up, we write back the contents to the file and reload the next
    // part of the bucket.
    for (i=0; i<256; i++) {
        while (current[i] != last[i]) {
            e = GetElement(i, current[i]);
            j = e->key[keyIndex];

            while (i != j) {
                pJ = GetElement(j, current[j]);
                temp = *pJ;
                *pJ  = *e;
                *e   = temp;
                current[j]++;
                FlushIfLast(fp, j, current[j], last[j]);
                j = temp.key[keyIndex];
            }
            current[i]++;
            FlushIfLast(fp, i, current[i], last[i]);
        }
    }

    // If we reached key[7], then we are done.
    if (keyIndex >= 7)
        return;

    // Now sort each bucket recursively.  If the bucket is small enough to
    // fit in fullCache, we sort it using qsort instead.
    keyIndex++;
    for (i=0; i<256; i++) {
        uint32_t bucketSize = (i > 0) ? current[i] - current[i-1] :
                                        current[0] - start;
        if (bucketSize > fullCacheMaxElements) {
            radixsort(fp, current[i] - bucketSize, current[i], keyIndex);
        } else if (bucketSize > 1) {
            qsortSegment(fp, current[i] - bucketSize, bucketSize);
        }
    }
}

int main(int argc, char *argv[])
{
    FILE    *fp        = NULL;
    uint32_t fileLen   = 0;
    uint32_t maxMemory = 16*1024*1024;

    if (argc < 2)
        exit(1);

    // Open file for read + write.
    fp = fopen(argv[1], "rb+");
    if (fp == NULL) {
        fprintf(stderr, "Couldn't open file: %s\n", argv[1]);
        exit(1);
    }

    if (argc > 2)
        maxMemory = atoi(argv[2]);

    // Round down max memory to a multiple of 256*sizeof(Element), because
    // we need to cut it into 256 equal pieces later.
    maxMemory = (maxMemory / (256*sizeof(Element))) * (256*sizeof(Element));

    // Allocate the full cache.
    fullCache = malloc(maxMemory);
    if (fullCache == NULL) {
        fprintf(stderr, "Out of memory\n");
        exit(1);
    }
    fullCacheMaxElements = maxMemory / sizeof(Element);

    // Carve the full cache into 256 equal pieces, one for each bucket.
    bucketMaxElements = fullCacheMaxElements / 256;
    for (int i=0;i<256;i++)
        cache[i].data = &fullCache[i * bucketMaxElements];

    // Find the length of the file.
    fseek(fp, 0, SEEK_END);
    fileLen = ftell(fp);

    // Sort the file in-place.
    radixsort(fp, 0, fileLen/sizeof(Element), 0);
    fclose(fp);
    free(fullCache);

    return 0;
}

I tested using a 140 MB file (10 million elements) full of random bytes. Here are some results:

Original Program, 256 MB:  13 seconds
Original Program,  64 MB:   2 minutes
Original Program,  16 MB:   5 minutes

Radix Sort      , 256 MB: 2.4 seconds
Radix Sort      ,   4 MB: 2.4 seconds
Radix Sort      ,   2 MB: 2.8 seconds
Radix Sort      ,   1 MB: 3.1 seconds
Radix Sort      , 512 KB: 4.9 seconds
Radix Sort      , 256 KB: 7.3 seconds
Radix Sort      , 128 KB:  12 seconds

I have a feeling that for very low memory limits, quicksort would do better than radix sort because the memory wouldn't need to be divided into 256 buffers. But radix sort appears to run at full speed starting at only 4 MB of memory (or 16KB buffer per bucket).

\$\endgroup\$
  • \$\begingroup\$ I have to say these times are plain impressive! I will need to change to uint64_t though but that won't be a problem. Thank you. I hope I get around to implementing this on my own. \$\endgroup\$ – BrainStone Sep 29 '16 at 7:30
4
\$\begingroup\$

Overall

As I mention in the comments. There is nothing that makes this code inherently C++ like. It basically looks like a C program that has been translated in C++; a few utility classes like std::fstream,std::string` and a few other are used incorrectly so you may as well have used the C counterparts and the program looks the same.

  • You do not take advantage of RAII (the biggest feature of C++).
  • Your use of new/delete is very C like and you don't take into account ownership semantics (one of the greatest failings in C).
    C++ very rarely uses RAW pointers and you always try and specify interfaces so that ownership is defined and thus lifespans controlled very tightly.
  • Your lack of using classes bogs your code down into using global mutable state a very bad pattern. That I am betting will make your threaded code hard to get correct.

Overall if you sent this in as the answer to an interview question for using C++ I would fail you and not give you the job. For a C job I suppose its OK.

Tools (Algorithms/Data structures/Iterators)

The C++ standard library contains a huge set of tools for you to use. You should learn them and use them rather than re-writting the wheel. std::sort() is a good example but the standard already has function to build and maintain a heap you don't need to write that yourself either.

Correctness

My initial thoughts were incorrect. The code works as expected.

Though it seems like some of the functions are not used (which threw my off). But with the test data provided I managed to run and validate the code as correct.

As it stands I am not convinced this code can actually sort a file larger than the cache. With a few fixes it could sort each section individually (each section being the size of the cache). But there is no code here that merges all the sorted sections together into a unified whole.

Given the two competing limitations I think this would be very hard to implement (though technically possible)

  • The files may be a lot larger than the available RAM.
  • The sorting has to occur in-place. No additional files may be created.

1) You either need to fit it all into memory to do the merge. 2) Use temporary files for each sorted section then merge into the destination file. 3) Do a complex dance of shuffling fields around the destination file as you do a merge sort into the destination file (this options does not seem attractive in the slightest).

Code Review

Using declarations.

Never do this.

using namespace std;

See every other code review. But you can find a detailed explanation here: Why is “using namespace std” considered bad practice?

Comments.

Useless comments are worse than no comments. The trouble with comments is that they need to be maintained (hence the concept of self documenting code). Your code should (function/variable names) should be written so that they are self documenting (which they are). If the name explains what it does there is little need to write a comment that says the same thing (as the comment needs to be maintained). If comments and code fall out of sync what does the maintainer do? Fix the comment to mach the code or fix the code to match the comment?

Good Comment:

// Sorts an idx file. Using chachSize bytes of RAM to speed it up.
void sortIDX( std::string idxFile, size_t cacheSize, bool quiet );

I get information from this comment about how the parameters are used. Though better parameter names may have achieved the same result.

Bad Comment:

// Writes the cache to the file
void writeFromCache();

If the comment is just echoing the function name then why have it?

Global Mutable State

streampos fileSize;
size_t numDataSets;
size_t limit;
atomic<size_t> pos;
fstream* file;
size_t arraySize = 0;
IndexEntry* cacheArray;

Bunch of file local variables! These variables maintain the state for the following set of functions. So only one thread can use these functions at a time.

Also this is basic encapsulation. By using a class you are saying that all these work together as a whole. A subsequent maintainer is not going to come along and re-use the variables in the wrong way (as the class links them all into a single state).

By just making this a class. Putting all those variables as members of the class and the following functions as methods you get a way to localize changes. Now independent threads can use the same functions without trading on the toes of other threads.

New/Delete

In modern C++ you rarely see new and the use of delete is even rarer. This is because RAW pointers do not convey ownership semantics. The owner of an object is the person responsible for deleting the object. Without ownership semantics it is unclear who should delete an object and this leads to a lot leaks and in bad cases double deletes.

So in modern C++ we use the concept of smart pointers to show ownership and its transfer of dynamically allocated objects. There are utility functions for correctly allocating objects and the destructor is used to delete the object.

Another way of doing memory management is via containers. These objects managee the memory for a group of objects.

IndexEntry* cacheArray;

Its hard to tell by the semantics here. But cacheArray represents a whole set of objects (which you manually manage the memory for). In C++ this may better be represented as:

std::vector<IndexEntry> cacheArray;

It not only manages the memory for the cache but expresses the intent that you have a whole set of objects here.

BUT this is only for the use case of dynamic objects. These are objects that live beyond the lifespan of their current scope. We usually prefer to use automatic (or in your case static) storage duration objects when possible and pass by reference (to show no ownership transfer). In these case the lifespan is well defined no runtime allocation is required.

Example 1:

{
    thread* sorterThread;
    // STUFF
    sorterThread = new thread( heapifyIDX, heapifyLimit );
    // STUFF BAD   
    sorterThread->join();
    delete sorterThread;
}

This is a classic case of a variable that should be automatic. Created at the point of declaration in the scope and destroy at the end of scope (thus tidying up automatically). By using this RAII mechanism you do not need to worry about exceptions (as the destrutor will always be called).

// Much more conical (and safer to write like this).
{
    // STUFF
    thread sorterThread( heapifyIDX, heapifyLimit );
    // STUFF BAD   
    sorterThread.join();
}

Example 2:

// Static storage duration object.
fstream* file;
// STUFF

{
    file = new fstream( idxFile, ios::in | ios::out | ios::binary | ios::ate );
    fileSize = file->tellg();

    // Lots of Stuff

    file->close();
    delete file;
}

Better way:

// Static storage duration object.
std::fstream file;

{
    try
    {
        file.open( idxFile, ios::in | ios::out | ios::binary | ios::ate );
        fileSize = file.tellg();

        // Lots of Stuff
    }
    catch(...)
    {
         file.close();
         // log error;
         throw;
    }
    file.close();
}

Best way:

{
    std::fstream file( idxFile, ios::in | ios::out | ios::binary | ios::ate );
    fileSize = file.tellg();

    // Lots of Stuff
    // pass file to associated functions.

} // File automatically closed.

Prefer C++ cast over C cast

        file->read( (char*)(cacheArray + i), writeSize );

This case (char*) is basically telling the compiler do this I know what I am doing. The problem is that it is very hard to spot (or search for) by a code reviewer/maintainer. C++ has an equivalent cast (for this situation) reinterpret_cast<char*>() much easier to spot and search for so that a code reviewer maintainer can see that you have a naughty part in your code and put some extra effort into the review.

Note: There are actually four types of C++ cast that all do slightly different things. static_cast<>(), const_cast<>(), reinterpret_cast<>() and dynamic_cast<>(). The first three are all compile time but do actually do some validation to make sure it is allowed. The fourth is a runtime cast.

Possible Bug:

In readIntoCache() and writeFromCache() you seek to the beginning of the file. This seems illogical as you can only ever sort the beginning of the file to a fixed size. You want to be able to sort from a fixed point in the file and write back to that fixed point after sorting.

Separation of Concerns

Also because of the way you have written the code you are breaking the principle Separation of Concerns as your buisness logic is intertwined with your resource management logic. You should separate the two into independent components.

Example:

In the functions readIntoCache() and writeFromCache() you have both resource management code (allocating/deallocating memory) and business logic (reading from the file).

If you move the resource management to std::vector<> then your logic becomes simpler and as a side affect your code will become more efficient as the reallocation of the memory will just reuse the memory previously allocated (with no work from you).

Do One thing in a function

The function sortIDX() is doing two things. It is sorting the file in one thread and maintaining a GUI display of progress. Sure you can do that but at least name the function appropriately.

You could divide the sort and display into two separate functions. Then use a third to call each independently it would definitely make the whole thing easier to use or use independently.

Heaps.

Rather than write your own heap sort you should probably use the built in one.

Strict Weak Ordering

Normally (i.e. traditionally) C++ uses operator<() to implement a strict weak ordering. There is not technically anything wrong with operator>() just seems a bit strange.

bool IndexEntry::operator>( const IndexEntry &lhs ) {
    for ( size_t i = 0; i < hashSize; i++ ) {
        if ( hash[i] > lhs.hash[i] )
            return true;
        else if ( hash[i] < lhs.hash[i] )
            return false;
    }

    return false;
}

But it does correctly implement a strict weak ordering (if your code needed to implement a stable sort though I would force myself to check the actual heap code to make sure it was still stable (since everybody is used to using the operator< it is much easier to spot that the function is stable that way).

You may also want to mark this method as const as it does not mutate the state of the object.

\$\endgroup\$
  • \$\begingroup\$ Thank you for your review. I read through it and have to agree. Most points you mentioned where a mere lack of practise in the last few months and your feedback helps me to get back to improve my coding. However I still want to adress a few points you mentioned. You have repeated several times that you doubt my code works and have repeatedly showed that you do not understand how I sort the file. I'm trying my best to explain it: I work with the file as an array. Let's say I have two spots in the file a and b. I read at a and store it to variable (in RAM) and do the same to spot. \$\endgroup\$ – BrainStone Sep 22 '16 at 20:57
  • \$\begingroup\$ The I write the data from spot a to spot b and the data from b to a. I esentially peformed a swap operation in the file. This enables me to sort the file. My cache partially stores a fixed part of the file to improve read and write access times. Since in heapsort the first elements are the ones that get read and moved the most I read the first elements of the file into the cache and write the changed (!!!) cache back to the file after sorting. \$\endgroup\$ – BrainStone Sep 22 '16 at 20:59
  • \$\begingroup\$ There are also two reasons why I can't use std::sort: First I have no way to tell the progress that way (see requirement #3). Second since my file is my "array" and I don't have a iterator like data strucure which would be required for the usage of the standard libary. Considering that I would need to write such an interface it was a lot simpler to write a heapsort implementation by my self. Also that way I can easily access the progress. So to summarize I agree with you on your formal review but the review of the programm itself is sadly wrong and useless. Thank you anyways. \$\endgroup\$ – BrainStone Sep 22 '16 at 21:04
  • \$\begingroup\$ I also have a short question. After I reviewed your suggestions and made the corresponding changes, should I ask a new question or update this with appropriate notes. \$\endgroup\$ – BrainStone Sep 22 '16 at 22:19
  • \$\begingroup\$ Ask a new question. \$\endgroup\$ – Martin York Sep 22 '16 at 22:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.