multithreading - Unable to get any speedup by making the huffman's algorithm parallel -


i trying implement huffman'a compression algorithm. right working on part of algorithm builds sequence table. idea count down number of times each letter occurs within text. text in case represented string read file. trying make counting of letters parallel. give each thread equal number of letters. unfortunately don't speedup. don't know might reason. use pthread_spinlock should no issue using since array small. see:

#include <string> #include <streambuf> #include <vector> #include <pthread.h> #include <stdio.h> #include <iostream> #include <string.h> #include <stdlib.h> #include <fstream> #include <memory> #include <errno.h> #include <time.h>  using namespace std;  void parse_arguments(int argc, char* const* const argv, bool& random_edges, int& vertex_count, int& threads_count, char* &input_file, char* &output_file, bool& enable_logging);  pthread_t * threads;  bool* used_threads; int used_threads_count; pthread_spinlock_t lock; struct dfs_args *thread_args;  int threads_count;  struct params  {    std::string text;    unsigned long long offset;    unsigned long long length; };  const int num_letters = 28; unsigned long long arr[num_letters];  void *parallel_huffman(void* args) {    unsigned long long arr_local[num_letters];    memset(arr_local, 0, sizeof(arr_local));      struct params* params = (struct params*)args;      unsigned long long start = params->offset;    unsigned long long length = params->length;    const string text = params->text;     (unsigned long long = start; < (start + length) && < (long long)text.size(); ++i)    {       if(text[i] >= 'a' && text[i] <= 'z')       {          int letter_offset = text[i] - 'a';          arr_local[letter_offset]++;        }        if(text[i] >= 'a' && text[i] <= 'z')       {          int letter_offset = text[i] - 'a';          arr_local[letter_offset]++;         }    }      pthread_spin_lock(&lock);       for( int = 0; < num_letters; ++i)       {          arr[i] += arr_local[i];       }     pthread_spin_unlock(&lock); }  int main(int argc, char* argv[]) {    double time_spent;    clock_t begin, end;    begin = clock();     threads_count = 0;    int cur_threads, vertex_count;     char* input_file = null, *output_file = null;    bool random_edges = false, enable_logging = true;;     memset(arr, 0, sizeof(arr));      vector<pthread_t> threads;    vector<params> parameters;    string text;     int ret = pthread_spin_init(&lock, pthread_process_shared);    if (ret != 0)    {       printf("failed init spin lock errno = %d\n", errno);       return -1;    }      parse_arguments(argc, argv, random_edges, vertex_count, threads_count, input_file, output_file, enable_logging);     ifstream input(input_file);     input.seekg(0, ios::end);     text.reserve(input.tellg());    input.seekg(0, ios::beg);     text.assign((istreambuf_iterator<char>(input)), istreambuf_iterator<char>());    //cout << text << endl;    input.close();  if (threads_count > 1) {    threads.reserve(threads_count);    parameters.reserve(threads_count);     unsigned long long len = text.size() / threads_count;     pthread_t thread;    struct params param;    unsigned long long i;    (i = 0; < threads_count; ++i)    {       struct params param;       param.text = text;       param.offset = i*len;       param.length = len;        parameters.push_back(param);       threads.push_back(thread);     }      long long last = parameters.size();    long long text_size = text.size();     parameters[last-1].length = text_size - parameters[last-1].offset;        (int = 0; < threads_count; ++i)    {        if (enable_logging)            printf("starting thread number %d\n", i);        if( pthread_create(&threads[i], null, parallel_huffman, &parameters[i]) )        {           printf("failed create thread");                 break;        }     } } else {    struct params param;    param.text = text;     param.offset = 0;    param.length = text.size();    parallel_huffman(&param); }    (int = 0; < threads_count; ++i)    {       if (enable_logging)          printf("awaiting thread number %d\n", i);       pthread_join(threads[i], null);    }    for( int = 0; < num_letters; ++i)    {       if (enable_logging)          printf("%c %llu\n", char('a' + i), arr[i]);    }       end = clock();    time_spent = (double)(end - begin) / clocks_per_sec;     if (enable_logging)        printf("total execution time of program -> %f\n", time_spent);    return 0; }   void parse_arguments(int argc, char* const* const argv, bool& random_edges, int& vertex_count, int& threads_count, char* &input_file, char* &output_file, bool& enable_logging) {    (int = 0; < argc; ++i)     {       if (0 == strcmp("-n", argv[i]) )       {          vertex_count = atoi(argv[i+1]);          random_edges = true;       } else if (0 == strcmp("-t", argv[i]) )       {          threads_count = atoi(argv[i+1]);       } else if (0 == strcmp("-f", argv[i]) )       {          input_file = argv[i+1];        } else if (0 == strcmp("-o", argv[i]) )       {          output_file = argv[i+1];       } else if (0 == strcmp("-q", argv[i]) )       {          enable_logging = false;       }     } }  


Comments

Popular posts from this blog

sql - invalid in the select list because it is not contained in either an aggregate function -

Angularjs unit testing - ng-disabled not working when adding text to textarea -

How to start daemon on android by adb -