Counting letters as quickly as possible

Question

I received a task, of taking a known text file (Linux dictionary), use threads to count the different letters in it, and present the results in an array.

The code doesn't have to be pretty, elegant, clean or short. The only demand is to count the letters correctly and do it as fast as possible. The file will be timed upon execution by using the time command, so every millisecond counts.

I know using a single thread may prove to be more efficient, but multithreading is a requirement here...

What I did so far:

• memory mapped the file so I can work with it from memory.
• used 4 threads so each of the 4 cores can do part of the job.
• avoided race conditions in design, so locks won't have to be used and spend time.
• tried to avoid calculations and unnecessary function calls.
• tried to get higher priority for my process.
• used register on variables whenever possible.

I am compiling the file with:

gcc count.c -o count -lpthread -Ofast

and running it as sudo su, hoping it will be higher priority.

I will be very happy if you could review my code and tell me where you think I can improve the speed (no matter how negligible you think it is).

Also, if you think something I did is pointless, please feel free to throw it in my face as well.

#include <stdio.h>
#include <fcntl.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/mman.h>
#include <pthread.h>
#include <sys/time.h>
#include <sys/resource.h>

/* declare counter arrays for the threads - global is quicker */
int counter[256];
int counter2[256];
int counter3[256];
int counter4[256];

/* declare a global pointer for the mapped file */
unsigned char* mapped_file;

/* declare variables for thread ids */
pthread_t pthread_id_1;
pthread_t pthread_id_2;
pthread_t pthread_id_3;
pthread_t pthread_id_4;

/* there are 4 functions that are declared independently, for each thread.
   it can be smarter, but we are looking for quick, not smart */
void* thread_func1(void* NotInUse)
{
    /* using register to quicken processing.
       234712 is a quarter of the size of the file */
    register int i1 = 234712;
    register int offset = 0;

    while (--i1)
    {
        ++counter[*(mapped_file +offset)];
        offset += 4;
    }

    return NULL;
}

void* thread_func2(void* NotInUse)
{
    register int i2 = 234712;
    register int offset = 1;
    while (--i2)
    {
        ++counter2[*(mapped_file +offset)];
        offset += 4;
    }

    return NULL;
}

void* thread_func3(void* NotInUse)
{
    register int i3 = 234712;
    register int offset = 2;
    while (--i3)
    {
        ++counter3[*(mapped_file +offset)];
        offset += 4;
    }

    return NULL;
}

void* thread_func4(void* NotInUse)
{
    register int i4 = 234713;
    register int offset = 3;
    while (--i4)
    {
        ++counter4[*(mapped_file + offset)];
        offset += 4;
    }

    return NULL;
}

/* main */

int main (int argc, char** arv, char** envp)

{
    /* trying to give my process a higher priority */
    setpriority(PRIO_PROCESS, 0, -20);

    /* open the text file */
    int fd = open("/usr/share/dict/american-english", O_RDONLY);

    /* map the text file. 938849 is its size */
    mapped_file = mmap((caddr_t)0, 938849, PROT_READ, MAP_SHARED, fd, 0);

    /* launching the treads */
    pthread_create(&pthread_id_1 , NULL , &thread_func1 , NULL );
    pthread_create(&pthread_id_2 , NULL , &thread_func2 , NULL );
    pthread_create(&pthread_id_3 , NULL , &thread_func3 , NULL );
    pthread_create(&pthread_id_4 , NULL , &thread_func4 , NULL );

    /* joining the threads */
    pthread_join( pthread_id_1 , NULL );
    pthread_join( pthread_id_2 , NULL );
    pthread_join( pthread_id_3 , NULL );
    pthread_join( pthread_id_4 , NULL );

    /* merging the individual counters */
    int i = 0;
    for ( i = 0 ; i < 256 ; ++ i)
    {
        counter[i] += counter2[i] + counter3[i] + counter4[i];
    }

    /* printing the final array
       (only to check it works, will be removed on the final run)*/
    i = 0;
    while (i < 256)
    {
    if (counter[i]) printf("%d. %d\n", i, counter[i]);
    ++i;
    }
    printf("Done\n");

    return 0;
}

Answer 1

Disclaimer: only an autopsy profiling may give an ultimate answer about performance.

That said, there is no miracles; the file is to be processed in an effectively sequential manner: every byte from the disk must be shipped into RAM, added up, and forgotten. The bottleneck is disk IO anyway. I have a gut feeling that memory mapping would create more problems than it is supposed to solve, due to a multitude of page faults it incurs.

I would rather go for double (or triple, or 4-way, or as much as needed) buffering, with one thread doing prefetch, and one thread doing the calculations.

Answer 2

Here are some things I saw that may help you improve your code.

Take care with memory access

First, in order to make the code fast you should strive to first make it correct and this code as posted is not quite correct. The original code's hardcoded filesize/4 has a problem in that the file size is not divisible by 4. As currently written, this is compensated by having the fourth thread get 234713 instead of 234712, but this is faulty math. The problem is that the code stops short of the actual end of the file. To demonstrate that for yourself, simply add up all of the counts. They should equal the file size, which is 938849 in your case, but instead they total 938845 which is 4 bytes short. Note that in the version I posted below, no math is required within the loop and the limit is precalculated to point to one beyond the end of the file. Not only does it work, but it will work no matter what the file size and no matter how many threads are used.

Use variables

Instead of having magic numbers like 938849 and 234712 within the code, it would make more sense to make them named variables. This increases the readability and maintainability of the code and costs nothing in terms of performance.

Eliminate unused variables

In this program argc, arv (which is typically spelled argv by the way) and envp are unused and should be eliminated from the program. Also, you have the NotInUse parameters passed to each of the threads. It's clear from the name that you know they're not being used, but they could be and should be as I'll show in a moment.

Pass structure pointers to threads

There is a lot of duplicated code here and a faulty assumption. Both can be neatly addressed with a small change to the code. The duplicated code is, of course, the four separate copies of the thread implementation. The faulty assumption is in the comments that say "we are looking for quick, not smart" and "global is quicker". Both assumption are faulty in that one can typically write code that is both smart and quick, and global variables are not necessarily quicker.

Here is a structure that can be passed to each thread.

struct tcount {
    size_t step;
    unsigned char *offset;
    unsigned char *limit;
    int counter[256];
};

void* thread_func(void* tcptr)
{
    struct tcount *t = tcptr;
    for (unsigned char *offset = t->offset; 
            offset < t->limit; offset += t->step)
    {
        ++(t->counter[*offset]);
    }
    return NULL;
}

Using this modification and the corresponding changes in main, I find that this code is consistently slightly faster than the original code, although the difference is small (37.45s for 10,000 iterations of the modified code vs 37.92s for 10,000 iterations of the original code).

Don't hardcode file sizes

Neither the particular file name nor the hard-coded file size are valid on my machine. To do a comparison, I had to modify your original code to point to /usr/share/dict/linux.words on my machine and use 4953680 which is the size of that file. It's even worse in that there are four copies of that size/4 (almost -- see the first point) which also all have to be hand-recoded. Better is to simply add this to main:

struct stat st;
stat(inputfilename, &st);

Now the file size is determined at runtime and never needs to be modified by the user, even if the file size is something different in the future. I can already hear your objection, "but I want it FAST!". However, my version of the code, with this addition actually runs faster than the original and is also easier to maintain. That's how you can code both quick and smart.

Eliminate global variables

My rewrite of this code uses no global variables, so clearly they are neither faster nor necessary. Eliminating them allows your code to be more readable and maintainable, both of which are important characteristics of well-written code. Global variables introduce messy linkages that are difficult to spot and error prone.

Check return values for errors

The calls to open and mmap can fail. You should check the return values to make sure they did not.

Use for loops where rational

The odd while loop at the end of main would be much more clearly written as a for loop. The same is true of each of the thread functions.

Consider alternative approaches

As was asked in one of the comments, one might try dividing the access in large chunks rather than interleaving. However this is difficult to modify in the original code, so you hadn't yet tried it. With the alterative thread code, it's simple to modify to try all kinds of different things including different numbers of threads. Here's the version of main I used:

/* determine how many threads to use */
#define THREADCOUNT 4
int main(void)
{
    static const char inputfilename[] = "/usr/share/dict/linux.words";
    /* trying to give my process a higher priority */
    setpriority(PRIO_PROCESS, 0, -20);

    /* open the text file */
    int fd = open(inputfilename, O_RDONLY);
    if (fd < 0) {
        printf("unable to open file: %s\n", inputfilename);
        return 1;
    }
    struct stat st;
    if (-1 == stat(inputfilename, &st)) {
        printf("unable to stat file %s\n", inputfilename);
        return 2;
    }
    off_t filesize = st.st_size;
    unsigned char* mapped_file = mmap(NULL, filesize, 
            PROT_READ, MAP_SHARED, fd, 0);

    if (mapped_file == (void *)-1) {
        printf("mmap of file %s failed\n", inputfilename);
        return 3;
    }
    static struct tcount tc[THREADCOUNT];
    memset(tc, 0, sizeof(struct tcount)*THREADCOUNT);
    /* this is interleaved; 
       modify values to try alternative strategies */
    for (int i=0; i<THREADCOUNT; ++i) {
        tc[i].limit = mapped_file+filesize; 
        tc[i].offset = mapped_file+i; 
        tc[i].step = THREADCOUNT; 
    }

    pthread_t thread_id[THREADCOUNT];
    for (int i=0; i < THREADCOUNT; ++i) {
        pthread_create(&thread_id[i], NULL , thread_func , &tc[i]);
    }

    /* joining the threads */
    for (int i=0; i < THREADCOUNT; ++i) {
        pthread_join(thread_id[i] , NULL);
    }

    /* merging the individual counters */
    for (int i = 0; i < 256 ; ++i)
    {
        for (int j=1; j < THREADCOUNT; ++j) {
            tc[0].counter[i] += tc[j].counter[i];
        }
    }

    unsigned bigtotal = 0;
    for (int i = 0 ; i < 256 ; ++i)
    {
        if (tc[0].counter[i]) 
            printf("%d. %d\n", i, tc[0].counter[i]);
        bigtotal += tc[0].counter[i];
    }
    printf("Done\n");
    printf("bigtotal = %u\n", bigtotal);
}

Note that pthread_create and pthread_join could fail. This code does not check for that but should.

Alternative strategy implementation (update)

Using this to initialize the threads, I was able to try a non-interleaved model.

for (int i=0; i<THREADCOUNT; ++i) {
    tc[i].limit = mapped_file+((i+1)*filesize/4); 
    tc[i].offset = mapped_file+(i*filesize/4); 
    tc[i].step = 1; 
}

I measured no difference in execution time.

Answer 3

Foreword

I'll be giving tips about the code you posted based on eye-visible code. However, a lot of optimizations come from what the compiler produced and failed to produce. To do that, you need to look at the assembly code, analyze it and fix manually what's wrong.

Misconceptions

and running it as sudo su, hoping it will be higher priority.

To get an higher priority than default, therefore to reduce it, you must have higher privileges; otherwise, setpriority will fail. To reduce your priority, you of course don't need to.

tried to avoid calculations and unnecessary function calls.

That's good. If you need performance, you can take out processing that can be pre-processed. But let the reader know what you have actually pre-processed!

mmap((caddr_t)0, 938849, PROT_READ, MAP_SHARED, fd, 0);

would be better if you defined a macro like: #define FILE_SIZE 938849

used register on variables whenever possible.

register does not guarantee that the qualified variable will be put in a register. It's only an hint to involve optimizations (like restrict). Point is that the compiler can figure out a register allocation scheme better than what you can; do you want to interfere with that (even though it won't likely be considered at all)?

/* declare counter arrays for the threads - global is quicker */ Somewhere the process will get that space from the stack and that's part of the execution time anyways (doesn't matter if it's before main or in main).

Suggestions

• int main (int argc, char** arv, char** envp) envp is not standard. Also, you aren't using any of them. Just use int main(void).

• Process your data contiguously: it will make your code easier yet better for the compiler to optimize and the CPU to process.

• You might use one, big array instead of 4: you'll pay for just one allocation. The threads will work on determined ranges of data.

• The counter for loop, although can be optimized (vectorized and unrolled), might benefit from parallel computation.