Results 1 to 16 of 16

Thread: Multithreaded synchronization: may not be needed sometimes?

  1. #1
    Member
    Join Date
    Dec 2013
    Location
    Italy
    Posts
    517
    Thanks
    25
    Thanked 45 Times in 37 Posts

    Multithreaded synchronization: may not be needed sometimes?

    I am working on a modification to a certain parallel execution program (ZPAQ !), using the venerable pthreads.

    I already know everything about traffic lights (!!!) aka semaphore, mutexes etc. (MS in computer science), but I'm reflecting on the actual mandatory under some relaxed assumptions.

    It is interesting, for me, to work in concrete cases, to see how the theory - which is taught as a dogma of faith - can materialize.

    Classic problem of the variable shared globally, between various threads.


    int globale=0;
    int contatore=0;

    (...)
    pthread ()
    int k=something();
    globale+=k;
    contatore++;


    (main)
    runs N thread, that generate different "something" values


    In this pseudo-code the two globals (globale and contatore) are changed directly by the threads.
    This is not good.

    Typically I would do this

    sem_t s; /* semaphore */
    (...)

    P(&s);
    globale+=k;
    contatore++;
    V(&s);

    (...)
    on whatever (a mutex)


    Suppose, however, that we has no interest in maintaining "perfect" global variable values.

    If, for some reason, they are changed erroneously (not updated, updated several times, zeroed or whatever) we don't care.
    Just statistical infos (#of compressed files, worked size etc)

    In this situation a modern CPU (with more cores, even on more separate dies) should still have an arbitration mechanism on RAM changes (for cache hierarchies, L1, L2 etc too).

    Is there a sort of HW mechanism for managing critical sections (portions of RAM, which are actually pages of virtual memory etc: in short it is extremely complex to establish what a simple "contatore++" does)?

    core/cpu 1
    move.l contatore, D0
    add.l #1, D0
    move.l D0, contatore

    core/cpu 2
    move.l contatore, D0
    add.l #1, D0
    move.l D0, contatore

    core/cpu 3
    move.l contatore, D0
    add.l #1, D0
    move.l D0, contatore
    (...)


    Such a pseudocode obviously triggers a series of enormous activities before becoming a "real" change to a physical RAM cell, even gigantic when using operating systems with virtual memory (as almost always)

    The question is: if it is NOT important that the global variables are perfectly up to date, can I safely (no CPU exception) avoid a semaphore or something like that (obviously reducing the latency, this is the ultimate goal)?

  2. #2
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,505
    Thanks
    26
    Thanked 136 Times in 104 Posts
    Have you considered atomics? They are good when your transaction scope is just a single variable and there's not a huge contention between threads (like several thousands updates per second).

    Atomics don't cause thread sleeping / parking / waiting / whatever you call it. If an update of atomic variable fails then the update is repeated. That works well if failure is happening not too often. The tradeoff threshold depends on how expensive is to recompute the operation. Simple addition of constant is very cheap, so it can be repeated quite a few times before atomics can be considered unfit for particular problem.

  3. #3
    Member
    Join Date
    Dec 2013
    Location
    Italy
    Posts
    517
    Thanks
    25
    Thanked 45 Times in 37 Posts
    Quote Originally Posted by Piotr Tarsa View Post
    Have you considered atomics? They are good when your transaction scope is just a single variable and there's not a huge contention between threads (like several thousands updates per second).

    Atomics don't cause thread sleeping / parking / waiting / whatever you call it. If an update of atomic variable fails then the update is repeated. That works well if failure is happening not too often. The tradeoff threshold depends on how expensive is to recompute the operation. Simple addition of constant is very cheap, so it can be repeated quite a few times before atomics can be considered unfit for particular problem.
    Atomic (std::atomic) is for C++ threads (std::threads)

  4. #4
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,505
    Thanks
    26
    Thanked 136 Times in 104 Posts
    Quote Originally Posted by fcorbelli View Post
    Atomic (std::atomic) is for C++ threads (std::threads)
    Erm, what? Atomics of course make sense only with multiple threads, but you don't need particular threads implementation to use them. Here you have the non-C++ version of atomics: https://en.cppreference.com/w/c/atomic https://en.cppreference.com/w/c/language/atomic

  5. #5
    Member
    Join Date
    Dec 2013
    Location
    Italy
    Posts
    517
    Thanks
    25
    Thanked 45 Times in 37 Posts
    Including
    #include <stdatomic.h>
    is not a really good idea, because you can get a gazillion of conflicts
    In file included from zpaq.cpp:127:0:
    c:\mingw\lib\gcc\x86_64-w64-mingw32\7.3.0\include\stdatomic.h:40:9: error: '_Atomic' does not name a type; did you mean '_wtoi'?
    typedef _Atomic _Bool atomic_bool;



    So you need to include

    #include <threads.h>

  6. #6
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,505
    Thanks
    26
    Thanked 136 Times in 104 Posts
    I don't know what exactly your requirements are. You say you can't do something or need to do something else, etc It wasn't even clear from the start if you want solution in C or C++.

    Here's my example of mixing C pthread.h with C++ atomic (and of course compiling with C++ compiler):
    Code:
    #include <cstdio>
    #include <pthread.h>
    #include <atomic>
    
    void *inc_cnt(void * cnt_void_ptr)
    {
      std::atomic<int> * cnt_ptr = (std::atomic<int> *) cnt_void_ptr;
      for (int i = 0; i < 100100100; i++) {
        (*cnt_ptr)++;
      }
      return NULL;
    }
    
    int main() {
      std::atomic<int> cnt = {0};
      printf("start cnt: %d\n", cnt.load());
      pthread_t inc_cnt_thread;
      if(pthread_create(&inc_cnt_thread, NULL, inc_cnt, &cnt)) {
        fprintf(stderr, "Error creating thread\n");
        return 1;
      }
      inc_cnt(&cnt);
      if(pthread_join(inc_cnt_thread, NULL)) {
        fprintf(stderr, "Error joining thread\n");
        return 2;
      }
      printf("final cnt: %d\n", cnt.load());
      return 0;
    }
    It works for me:
    Code:
    $ g++ -pthread atomics.cpp
    $ ./a.out 
    start cnt: 0
    final cnt: 200200200

  7. #7
    Member
    Join Date
    Dec 2013
    Location
    Italy
    Posts
    517
    Thanks
    25
    Thanked 45 Times in 37 Posts
    This one
    Attached Files Attached Files

  8. #8
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,505
    Thanks
    26
    Thanked 136 Times in 104 Posts
    How to compile it under Linux (I have Ubuntu 18.04.5)? I keep getting errors like this:
    Code:
    zpaq.cpp:7871:14: error: ‘HN_DIVISOR_1000’ was not declared in this scope
      if (flags & HN_DIVISOR_1000) {
                  ^~~~~~~~~~~~~~~
    zpaq.cpp:7874:15: error: ‘HN_B’ was not declared in this scope
       if (flags & HN_B)
                   ^~~~
    zpaq.cpp:7884:15: error: ‘HN_B’ was not declared in this scope
       if (flags & HN_B)
                   ^~~~
    zpaq.cpp:7894:16: error: ‘HN_AUTOSCALE’ was not declared in this scope
          (scale & (HN_AUTOSCALE | HN_GETSCALE)) == 0)
                    ^~~~~~~~~~~~
    zpaq.cpp:7894:31: error: ‘HN_GETSCALE’ was not declared in this scope
          (scale & (HN_AUTOSCALE | HN_GETSCALE)) == 0)
                                   ^~~~~~~~~~~
    zpaq.cpp:7894:31: note: suggested alternative: ‘F_GET_SEALS’
          (scale & (HN_AUTOSCALE | HN_GETSCALE)) == 0)
                                   ^~~~~~~~~~~
                                   F_GET_SEALS
    zpaq.cpp:7911:14: error: ‘HN_NOSPACE’ was not declared in this scope
      if (flags & HN_NOSPACE)
                  ^~~~~~~~~~
    Also what's the encoding of that file? It probably isn't UTF-8 as gedit complains.

  9. #9
    Member
    Join Date
    Dec 2013
    Location
    Italy
    Posts
    517
    Thanks
    25
    Thanked 45 Times in 37 Posts
    I do not use Linux, but Windows and Unix (FreeBSD and Solaris)
    Compile instructions are in the first lines, under FreeBSD for example is

    gcc7 -O3 -march=native -Dunix zpaq.cpp -static -lstdc++ libzpaq.cpp -pthread -o zpaq -static -lm

    the file is coded in ANSI

  10. #10
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,505
    Thanks
    26
    Thanked 136 Times in 104 Posts
    Hmm,
    Code:
    $ gcc -O3 -march=native -Dunix zpaq.cpp -static -lstdc++ libzpaq.cpp -pthread -o zpaq -static -lm > errors.txt 2>&1
    gives me:
    Code:
    zpaq.cpp: In function ‘bool comparecrc32block(s_crc32block, s_crc32block)’:
    zpaq.cpp:3001:40: warning: format ‘%lld’ expects argument of type ‘long long int’, but argument 3 has type ‘uint64_t {aka long unsigned int}’ [-Wformat=]
      sprintf(a_start,"%014lld",a.crc32start);
                                ~~~~~~~~~~~~^
    zpaq.cpp:3002:40: warning: format ‘%lld’ expects argument of type ‘long long int’, but argument 3 has type ‘uint64_t {aka long unsigned int}’ [-Wformat=]
      sprintf(b_start,"%014lld",b.crc32start);
                                ~~~~~~~~~~~~^
    zpaq.cpp: In function ‘void mygetch()’:
    zpaq.cpp:3202:17: error: aggregate ‘mygetch()::termios oldt’ has incomplete type and cannot be defined
      struct termios oldt, newt;
                     ^~~~
    zpaq.cpp:3202:23: error: aggregate ‘mygetch()::termios newt’ has incomplete type and cannot be defined
      struct termios oldt, newt;
                           ^~~~
    zpaq.cpp:3203:2: error: ‘tcgetattr’ was not declared in this scope
      tcgetattr ( STDIN_FILENO, &oldt );
      ^~~~~~~~~
    zpaq.cpp:3203:2: note: suggested alternative: ‘tcgetpgrp’
      tcgetattr ( STDIN_FILENO, &oldt );
      ^~~~~~~~~
      tcgetpgrp
    zpaq.cpp:3205:21: error: ‘ICANON’ was not declared in this scope
      newt.c_lflag &= ~( ICANON | ECHO );
                         ^~~~~~
    zpaq.cpp:3205:30: error: ‘ECHO’ was not declared in this scope
      newt.c_lflag &= ~( ICANON | ECHO );
                                  ^~~~
    zpaq.cpp:3205:30: note: suggested alternative: ‘EIO’
      newt.c_lflag &= ~( ICANON | ECHO );
                                  ^~~~
                                  EIO
    zpaq.cpp:3206:28: error: ‘TCSANOW’ was not declared in this scope
      tcsetattr ( STDIN_FILENO, TCSANOW, &newt );
                                ^~~~~~~
    zpaq.cpp:3206:28: note: suggested alternative: ‘TCSETAW’
      tcsetattr ( STDIN_FILENO, TCSANOW, &newt );
                                ^~~~~~~
                                TCSETAW
    zpaq.cpp:3206:2: error: ‘tcsetattr’ was not declared in this scope
      tcsetattr ( STDIN_FILENO, TCSANOW, &newt );
      ^~~~~~~~~
    zpaq.cpp:3206:2: note: suggested alternative: ‘tcsetpgrp’
      tcsetattr ( STDIN_FILENO, TCSANOW, &newt );
      ^~~~~~~~~
      tcsetpgrp
    zpaq.cpp: In function ‘int myhuman(char*, size_t, int64_t, const char*, int, int)’:
    zpaq.cpp:7869:14: error: ‘HN_DIVISOR_1000’ was not declared in this scope
      if (flags & HN_DIVISOR_1000) {
                  ^~~~~~~~~~~~~~~
    zpaq.cpp:7872:15: error: ‘HN_B’ was not declared in this scope
       if (flags & HN_B)
                   ^~~~
    zpaq.cpp:7882:15: error: ‘HN_B’ was not declared in this scope
       if (flags & HN_B)
                   ^~~~
    zpaq.cpp:7892:16: error: ‘HN_AUTOSCALE’ was not declared in this scope
          (scale & (HN_AUTOSCALE | HN_GETSCALE)) == 0)
                    ^~~~~~~~~~~~
    zpaq.cpp:7892:31: error: ‘HN_GETSCALE’ was not declared in this scope
          (scale & (HN_AUTOSCALE | HN_GETSCALE)) == 0)
                                   ^~~~~~~~~~~
    zpaq.cpp:7892:31: note: suggested alternative: ‘F_GET_SEALS’
          (scale & (HN_AUTOSCALE | HN_GETSCALE)) == 0)
                                   ^~~~~~~~~~~
                                   F_GET_SEALS
    zpaq.cpp:7909:14: error: ‘HN_NOSPACE’ was not declared in this scope
      if (flags & HN_NOSPACE)
                  ^~~~~~~~~~
    zpaq.cpp:7909:14: note: suggested alternative: ‘N_6PACK’
      if (flags & HN_NOSPACE)
                  ^~~~~~~~~~
                  N_6PACK
    zpaq.cpp:7921:15: error: ‘HN_AUTOSCALE’ was not declared in this scope
      if (scale & (HN_AUTOSCALE | HN_GETSCALE)) {
                   ^~~~~~~~~~~~
    zpaq.cpp:7921:30: error: ‘HN_GETSCALE’ was not declared in this scope
      if (scale & (HN_AUTOSCALE | HN_GETSCALE)) {
                                  ^~~~~~~~~~~
    zpaq.cpp:7921:30: note: suggested alternative: ‘F_GET_SEALS’
      if (scale & (HN_AUTOSCALE | HN_GETSCALE)) {
                                  ^~~~~~~~~~~
                                  F_GET_SEALS
    zpaq.cpp:7936:38: error: ‘HN_DECIMAL’ was not declared in this scope
      if (bytes < 995 && i > 0 && flags & HN_DECIMAL) {
                                          ^~~~~~~~~~
    zpaq.cpp: In function ‘void tohuman(long long int, char*)’:
    zpaq.cpp:7959:10: error: ‘HN_B’ was not declared in this scope
      flags = HN_B | HN_NOSPACE | HN_DECIMAL;
              ^~~~
    zpaq.cpp:7959:17: error: ‘HN_NOSPACE’ was not declared in this scope
      flags = HN_B | HN_NOSPACE | HN_DECIMAL;
                     ^~~~~~~~~~
    zpaq.cpp:7959:17: note: suggested alternative: ‘N_6PACK’
      flags = HN_B | HN_NOSPACE | HN_DECIMAL;
                     ^~~~~~~~~~
                     N_6PACK
    zpaq.cpp:7959:30: error: ‘HN_DECIMAL’ was not declared in this scope
      flags = HN_B | HN_NOSPACE | HN_DECIMAL;
                                  ^~~~~~~~~~
    zpaq.cpp:7960:11: error: ‘HN_DIVISOR_1000’ was not declared in this scope
      flags |= HN_DIVISOR_1000;
               ^~~~~~~~~~~~~~~
    zpaq.cpp:7962:17: error: ‘HN_AUTOSCALE’ was not declared in this scope
          bytes, "", HN_AUTOSCALE, flags);
                     ^~~~~~~~~~~~
    zpaq.cpp: In function ‘long long int getfreespace(const char*)’:
    zpaq.cpp:7968:16: error: aggregate ‘getfreespace(const char*)::statfs stat’ has incomplete type and cannot be defined
      struct statfs stat;
                    ^~~~
    zpaq.cpp:7970:26: error: invalid use of incomplete type ‘struct getfreespace(const char*)::statfs’
      if (statfs(i_path, &stat) != 0) 
                              ^
    zpaq.cpp:7968:9: note: forward declaration of ‘struct getfreespace(const char*)::statfs’
      struct statfs stat;
             ^~~~~~
    zpaq.cpp:7982:3: error: ‘getbsize’ was not declared in this scope
       getbsize(&dummy, &blocksize);
       ^~~~~~~~
    zpaq.cpp:7982:3: note: suggested alternative: ‘getsid’
       getbsize(&dummy, &blocksize);
       ^~~~~~~~
       getsid
    zpaq.cpp: In member function ‘int Jidac::summa()’:
    zpaq.cpp:8403:103: warning: embedded ‘\0’ in format [-Wformat-contains-nul]
          sprintf(p->second.sha1hex,"%08X\0x0",crc32_calc_file(filename.c_str(),inizio,total_size,lavorati));
                                                                                                           ^
    zpaq.cpp:8409:104: warning: embedded ‘\0’ in format [-Wformat-contains-nul]
          sprintf(p->second.sha1hex,"%08X\0x0",crc32c_calc_file(filename.c_str(),inizio,total_size,lavorati));
                                                                                                            ^
    zpaq.cpp:8416:53: warning: format ‘%llX’ expects argument of type ‘long long unsigned int’, but argument 3 has type ‘uint64_t {aka long unsigned int}’ [-Wformat=]
          sprintf(p->second.sha1hex,"%016llX\0x0",result2);
                                                         ^
    zpaq.cpp:8416:53: warning: embedded ‘\0’ in format [-Wformat-contains-nul]
    zpaq.cpp:8488:76: warning: format ‘%lld’ expects argument of type ‘long long int’, but argument 2 has type ‘int64_t {aka long int}’ [-Wformat=]
       printf("Worked on %lld average speed %s B/s\n",lavorati,migliaia(myspeed));
                                                                                ^
    zpaq.cpp: In function ‘int unz(const char*, const char*, bool)’:
    zpaq.cpp:11231:116: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘long unsigned int’ [-Wformat=]
       printf("%02d frags %s (RAM used ~ %s)\r",100-(offset*100/(total_size+1)),migliaia(frag.size()),migliaia2(ramsize));
                                                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~                                         ^
    zpaq.cpp:11286:140: warning: format ‘%lld’ expects argument of type ‘long long int’, but argument 2 has type ‘unsigned int’ [-Wformat=]
           printf("File %08lld of %08lld (%20s) %1.3f %s\n",i+1,(long long)mappadt.size(),migliaia(size),(mtime()-startrecalc)/1000.0,fn.c_str());
                                                            ~~~                                                                                 ^
    zpaq.cpp: In member function ‘int Jidac::test()’:
    zpaq.cpp:11721:58: warning: format ‘%lu’ expects argument of type ‘long unsigned int’, but argument 2 has type ‘unsigned int’ [-Wformat=]
         printf("Block %08lu K %s\r",i/1000,migliaia(lavorati));
                                     ~~~~~~                   ^
    zpaq.cpp:11839:102: warning: format ‘%X’ expects argument of type ‘unsigned int’, but argument 3 has type ‘const char*’ [-Wformat=]
           printf("SURE:  STORED %08X = DECOMPRESSED = FROM FILE %08Xn",crc32stored,filedefinitivo.c_str());
                                                                                    ~~~~~~~~~~~~~~~~~~~~~~^
    zpaq.cpp:11852:89: warning: format ‘%X’ expects argument of type ‘unsigned int’, but argument 3 has type ‘const char*’ [-Wformat=]
          printf("GOOD: STORED %08X = DECOMPRESSED %08X\n",crc32stored,filedefinitivo.c_str());
                                                                       ~~~~~~~~~~~~~~~~~~~~~~^
    zpaq.cpp: In function ‘bool comparefilenamesize(s_fileandsize, s_fileandsize)’:
    zpaq.cpp:11962:33: warning: format ‘%lld’ expects argument of type ‘long long int’, but argument 3 has type ‘uint64_t {aka long unsigned int}’ [-Wformat=]
      sprintf(a_size,"%014lld",a.size);
                               ~~~~~~^
    zpaq.cpp:11963:33: warning: format ‘%lld’ expects argument of type ‘long long int’, but argument 3 has type ‘uint64_t {aka long unsigned int}’ [-Wformat=]
      sprintf(b_size,"%014lld",b.size);
                               ~~~~~~^
    zpaq.cpp: In function ‘bool comparefilenamedate(s_fileandsize, s_fileandsize)’:
    zpaq.cpp:11970:33: warning: format ‘%lld’ expects argument of type ‘long long int’, but argument 3 has type ‘int64_t {aka long int}’ [-Wformat=]
      sprintf(a_size,"%014lld",a.date);
                               ~~~~~~^
    zpaq.cpp:11971:33: warning: format ‘%lld’ expects argument of type ‘long long int’, but argument 3 has type ‘int64_t {aka long int}’ [-Wformat=]
      sprintf(b_size,"%014lld",b.date);
                               ~~~~~~^
    zpaq.cpp: In member function ‘int Jidac::dir()’:
    zpaq.cpp:12008:39: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘std::vector<std::__cxx11::basic_string<char> >::size_type {aka long unsigned int}’ [-Wformat=]
      printf("FIles.size %d\n",files.size());
                               ~~~~~~~~~~~~^
    zpaq.cpp:12108:87: warning: format ‘%d’ expects argument of type ‘int’, but argument 3 has type ‘uint64_t {aka long unsigned int}’ [-Wformat=]
         printf("PRE %08d  %08d %s\n",i,fileandsize[i].size,fileandsize[i].filename.c_str());
                                                                                           ^
    zpaq.cpp:12118:88: warning: format ‘%d’ expects argument of type ‘int’, but argument 3 has type ‘uint64_t {aka long unsigned int}’ [-Wformat=]
         printf("POST %08d  %08d %s\n",i,fileandsize[i].size,fileandsize[i].filename.c_str());
                                                                                            ^
    zpaq.cpp:12176:173: warning: format ‘%ld’ expects argument of type ‘long int’, but argument 2 has type ‘int’ [-Wformat=]
            printf("%08ld CRC-1 %08X %s %19s %s\n",i,fileandsize[i].crc32,dateToString(fileandsize[i].date).c_str(),migliaia(fileandsize[i].size),fileandsize[i].filename.c_str());
                                                                                                                                                                                 ^
    zpaq.cpp:12181:39: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘int64_t {aka long int}’ [-Wformat=]
            printf("Done %03d ",percentuale);
                                           ^
    zpaq.cpp:12204:182: warning: format ‘%ld’ expects argument of type ‘long int’, but argument 2 has type ‘int’ [-Wformat=]
           printf("%08ld CRC-2 %08X %s %19s %s\n",i+1,fileandsize[i+1].crc32,dateToString(fileandsize[i+1].date).c_str(),migliaia(fileandsize[i+1].size),fileandsize[i+1].filename.c_str());
                                                  ~~~                                                                                                                                     ^
    zpaq.cpp:12209:38: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘int64_t {aka long int}’ [-Wformat=]
           printf("Done %03d ",percentuale);
                                          ^
    zpaq.cpp:12250:88: warning: format ‘%ld’ expects argument of type ‘long int’, but argument 2 has type ‘int’ [-Wformat=]
         printf("%ld size %s <<%08X>>\n",i,migliaia(fileandsize.size()),fileandsize[i].crc32);
                                                                                            ^
    zpaq.cpp:12260:38: warning: format ‘%ld’ expects argument of type ‘long int’, but argument 2 has type ‘int’ [-Wformat=]
       printf("Limit founded %ld\n",limite);
                                          ^
    zpaq.cpp:12353:71: warning: format ‘%ld’ expects argument of type ‘long int’, but argument 2 has type ‘int’ [-Wformat=]
      printf("  %8ld File     %19s byte\n",quantifiles,migliaia(total_size));
                                                                           ^
    zpaq.cpp:12355:43: warning: format ‘%ld’ expects argument of type ‘long int’, but argument 2 has type ‘int’ [-Wformat=]
      printf("  %8ld directory",quantedirectory);
                                               ^
    zpaq.cpp: In member function ‘int Jidac::dircompare()’:
    zpaq.cpp:12709:61: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘std::vector<std::__cxx11::basic_string<char> >::size_type {aka long unsigned int}’ [-Wformat=]
      printf("Dir compare (%d dirs to be checked)\n",files.size());
                                                     ~~~~~~~~~~~~^
    zpaq.cpp:12769:51: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘std::vector<std::__cxx11::basic_string<char> >::size_type {aka long unsigned int}’ [-Wformat=]
       printf("Creating %d scan threads\n",files.size());
                                           ~~~~~~~~~~~~^
    I have
    Code:
    $ gcc --version
    gcc (Ubuntu 7.5.0-3ubuntu1~18.04) 7.5.0
    Copyright (C) 2017 Free Software Foundation, Inc.
    Anyway, have you tried inserting my code somewhere in your code and then compiling it?

  11. #11
    Member
    Join Date
    Dec 2013
    Location
    Italy
    Posts
    517
    Thanks
    25
    Thanked 45 Times in 37 Posts
    Including

    #include <atomic>


    and declaring

    atomic_int64_t g_bytescanned;
    atomic_int64_t g_filescanned;

    compile on Windows, but not on FreeBSD


    paq.cpp:356:1: error: 'atomic_int64_t' does not name a type; did you mean 'u_int64_t'?
    atomic_int64_t g_bytescanned;

  12. #12
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,505
    Thanks
    26
    Thanked 136 Times in 104 Posts
    What if you use `std::atomic<std::int64_t>` instead of its alias `atomic_int64_t`?

  13. #13
    Member
    Join Date
    Dec 2013
    Location
    Italy
    Posts
    517
    Thanks
    25
    Thanked 45 Times in 37 Posts
    I will make a debian virtual machine and fix the BSD-dependent code.

    But the question is always the same of the first post.

    In a multithreaded system with multiple cores and an operating system with virtual memory
    (windows, linux, unix), can you have a CPU exception when two instructions modify the same memory cell?

    Or does the content simply become not well defined?

  14. #14
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,505
    Thanks
    26
    Thanked 136 Times in 104 Posts
    Quote Originally Posted by fcorbelli View Post
    But the question is always the same of the first post.

    In a multithreaded system with multiple cores and an operating system with virtual memory
    (windows, linux, unix), can you have a CPU exception when two instructions modify the same memory cell?

    Or does the content simply become not well defined?
    Well, there are many things at play:
    1) there should be no exception on write, whatever that means. One thread will win the race. However, when you read the value back it could be in inconsistent state, e.g. one thread won with one part of result, other thread won with other part of result, so in the end the result is corrupted and using it will result in exception, segfault, etc
    2) there is always some transaction size. I think that if you have a register of size 2^N bytes and you write to a memory location aligned at 2^N bytes then your write will either succeed fully or will be overwritten fully. This means that if you e.g. store a pointer to a field aligned to pointer size then it will either suceed fully or be overwritten fully by another thread. In either case there will be a valid pointer if both threads write valid pointers.
    3) you need to be aware of https://en.wikipedia.org/wiki/Memory..._(programming) and https://en.wikipedia.org/wiki/Consistency_model . For example if you don't place volatile nor atomic modifiers then compiler is allowed to cache the value in register and potentially update the real memory cell very rarely. If you don't use memory fences (atomics trigger memory fences) then CPU core could delay updating other cores so that the other core would get stale data.
    4) transformations (e.g. addition) are done on CPU level, so CPU needs to invoke many steps: load value, change value, store value. Since there are multiple steps, another CPU core could access the data in between steps of the first core. Therefore to implement atomics instructions like https://en.wikipedia.org/wiki/Compare-and-swap are needed to verify at the end of transformation that the original value is still at the original memory location. If not, then compare-exchange instruction fails and whole transformation is repeated. Such process is repeated until compare-exchange achieves success. In case of reasonably low contention between threads the success rate is high.
    5) the CPU instructions define the guarantees you'll see in practice. So if you copy 8 bytes one byte at a time and two threads are doing that on the same memory location then you won't get the guarantees of 8-byte writes done as single instruction.
    6) on some CPUs (e.g. ARM ones) there are only aligned writes, so compiler has to emulate unaligned writes using aligned writes. For example if you write 4 bytes at memory address 13. 13 % 4 != 0, so compiler need to issue two 4-byte writes, each transforming data that's already there. Because there is a multi-step non-atomic transformation there could be corruption of data if multiple threads access the memory location.

  15. Thanks:

    Bulat Ziganshin (12th January 2021)

  16. #15
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    4,135
    Thanks
    320
    Thanked 1,397 Times in 802 Posts
    > The question is: if it is NOT important that the global variables are
    > perfectly up to date, can I safely (no CPU exception) avoid a semaphore or
    > something like that (obviously reducing the latency, this is the ultimate goal)?

    On x86 yes, though you'd have to add "volatile" specifier to the variables
    accessed from multiple threads.

    On some weird platforms like PPC and embedded ones you might also need
    explicit cache flushes and/or or intrinsics like __sync_synchronize().

    So yes, on x86 its quite possible to implement MT without explicit semaphores -
    its simply less efficient when a thread spins a loop waiting for some global variable,
    while with thread APIs it could release the core to OS while it waits.

    There're also some interesting new tools:
    https://gcc.gnu.org/onlinedocs/gcc-4...ntrinsics.html

  17. Thanks:

    fcorbelli (11th January 2021)

  18. #16
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    4,135
    Thanks
    320
    Thanked 1,397 Times in 802 Posts
    > In a multithreaded system with multiple cores and an operating system with virtual memory
    > (windows, linux, unix), can you have a CPU exception when two instructions modify the same memory cell?

    No, there're no exceptions for this.
    Just that a "global variable" without "volatile" might be actually kept in a register.

    > Or does the content simply become not well defined?

    In a sense. You just can't predict the order of read/write operations working in different threads.

Similar Threads

  1. Replies: 9
    Last Post: 16th February 2019, 09:30
  2. Replies: 0
    Last Post: 1st December 2013, 18:54
  3. Multithreaded merge BWT/ST
    By Bulat Ziganshin in forum Data Compression
    Replies: 7
    Last Post: 5th September 2012, 19:54
  4. 4x4 - multithreaded compressor
    By Bulat Ziganshin in forum Forum Archive
    Replies: 12
    Last Post: 19th April 2008, 18:25
  5. CCM(x) multithreaded ?
    By SvenBent in forum Forum Archive
    Replies: 2
    Last Post: 15th September 2007, 16:29

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •