Cela dépend du modèle d'accès, avez-vous un moyen de partitionner le travail efficacement? Fondamentalement, vous pouvez partitionner le tableau en 8 morceaux (ou autant que vous pouvez vous le permettre) et couvrir chaque partie avec un mutex, mais si le modèle d'accès est aléatoire, vous allez toujours avoir beaucoup de collisions.

Avez-vous le support TSX sur votre système? ce serait un exemple classique, avoir juste un verrou global et faire en sorte que les threads l'ignorent à moins qu'il y ait une collision réelle.

Réfléchir à haute voix ici ... et pas vraiment sûr de son efficacité, mais:

Vous pouvez créer une méthode de verrouillage de certains index:

vector<int> mutexed_slots;
std::mutex mtx;

bool lock_element(int index) 
{
    std::lock_guard<std::mutex> lock(mtx);
    // Check if item is in the mutexed list
    if ( !std::find(mutexed_slots.begin(), mutexed_slots.end(), index) != vector.end() ) 
    {
       // If its not then add it - now that array value is safe from other threads
       mutexed_slots.emplace_back(index);
       return true;
    }
    return false;
}

void unlock_element(int index) 
{
    std::lock_guard<std::mutex> lock(mtx);
    // No need to check because you will only unlock the element that you accessed (unless you are a very naughty boy indeed)
    vec.erase(vec.begin() + index);
}

Remarque: C'est le début d'une idée, alors ne la frappez pas trop fort pour l'instant! Son pseudo-code également non testé. Ce n'est pas vraiment une réponse finale - mais un point de départ. Veuillez ajouter des commentaires pour améliorer ou suggérer que ce n'est pas plausible.

Autres points:

• Il existe peut-être une STL plus efficace à utiliser
• Vous pourriez probablement regrouper tout cela dans un cours avec vos données
• Vous auriez besoin de parcourir lock_element () jusqu'à ce qu'il renvoie true - encore une fois pas joli pour le moment. Ce mécanisme pourrait être amélioré.
• Chaque thread doit se souvenir sur quel index il travaille actuellement afin de ne déverrouiller que celui-là - encore une fois, cela pourrait être plus intégré dans une classe pour garantir ce comportement.

Mais en tant que concept - réalisable? Je pense que si vous avez besoin d'un accès très rapide (ce que vous faites peut-être), cela pourrait ne pas être aussi efficace, pensées?

Mettre à jour

Cela pourrait être fait beaucoup plus efficace si chaque thread / worker "enregistre" sa propre entrée dans mutexed_slots . Ensuite, il n'y aurait pas de push_back / remove du vecteur (sauf au début / à la fin). Ainsi, chaque thread définit simplement l'index qu'il a verrouillé - s'il n'a rien de verrouillé, il est simplement défini sur -1 (ou tel). Je pense qu'il y a encore beaucoup d'autres améliorations d'efficacité à apporter. Encore une fois, une classe complète pour faire tout cela pour vous serait le moyen de l'implémenter.

Test / Résultats

J'ai implémenté un testeur pour cela, juste parce que j'apprécie beaucoup ce genre de chose. Ma mise en œuvre est ici

Je pense que c'est un dépôt github public - donc vous êtes invités à y jeter un œil. Mais j'ai posté les résultats sur le readme de niveau supérieur (donc faites défiler un peu pour les voir). J'ai implémenté quelques améliorations telles que:

• Il n'y a pas d'insertion / suppression dans le tableau de protection au moment de l'exécution

• Il n'y a pas besoin d'un lock_guard pour faire le "déverrouillage" car je ne me fie pas à un index std :: atomic.

  Voici une impression de mon résumé:

Summary:

Lorsque la charge de travail est de 1 ms (le temps nécessaire pour effectuer chaque action), la quantité de travail effectuée était de:

• 9808 pour protégé

• 8117 pour normal

Lorsque la charge de travail est de 0 ms (incrémenter de quelques compteurs), la quantité de travail effectuée était de:

• 9791264 pour protégé
• 29307829 pour normal

Vous pouvez donc voir ici que l'utilisation de la protection mutex ralentit le travail d'un facteur d'environ un tiers (1/3). Ce ratio est cohérent entre les tests.

J'ai également exécuté les mêmes tests pour 1 worker, et les mêmes ratios se sont à peu près vérifiés. Cependant, lorsque je réduis le tableau (~ 1000 éléments), la quantité de travail effectuée est toujours à peu près la même lorsque la charge de travail est de 1 ms. Mais lorsque la charge de travail est très légère, j'ai obtenu des résultats comme:

• 5621311

• 39157931

  Ce qui est environ 7 fois plus lent.

Conclusion

• Plus le tableau est grand, moins il y a de collisions - les performances sont meilleures.
• Plus la charge de travail est longue (par élément), moins la différence est notable avec l'utilisation du mécanisme de protection.

Il semble que le verrouillage ne fait généralement qu'ajouter une surcharge qui est 2 à 3 fois plus lente puis incrémenter quelques compteurs. Ceci est probablement faussé par les collisions réelles car (d'après les résultats) le temps de verrouillage le plus long enregistré était de 40 ms - mais c'était à l'époque où le temps de travail était très rapide, donc de nombreuses collisions se sont produites (~ 8 verrous réussis par collision).

Vous pouvez écrire une classe qui créera des verrous à la volée lorsqu'un index particulier l'exige, std :: optional serait utile pour cela (code C ++ 17 à l'avance):

constexpr size_t kLockLimit = 8;
IndexLocker index_locker(kLockLimit);

auto thread_code = [&](size_t i) {
    std::lock_guard guard(index_locker.get_lock(i % kLockLimit));
    // Do work with lock.
};

Vous pouvez également utiliser std :: unique_ptr pour minimiser l'espace de pile mais conserver une sémantique identique:

class IndexLocker {
  public:
    explicit IndexLocker(size_t size) : index_locks_(size) {}

    std::mutex& get_lock(size_t i) {
        if (std::lock_guard guard(instance_lock_); index_locks_[i] == nullptr) {
            index_locks_[i] = std::make_unique<std::mutex>();
        }
        return *index_locks_[i];
    }

  private:
    std::vector<std::unique_ptr<std::mutex>> index_locks_;
    std::mutex instance_lock_;
};

L'utilisation de cette classe ne signifie pas nécessairement que vous devez créer les 1 000 000 éléments. Vous pouvez utiliser des opérations modulo pour traiter le casier comme une "table de hachage" de mutex:

class IndexLocker {
  public:
    explicit IndexLocker(size_t size) : index_locks_(size) {}

    std::mutex& get_lock(size_t i) {
        if (std::lock_guard guard(instance_lock_); index_locks_[i] == std::nullopt) {
            index_locks_[i].emplace();
        }
        return *index_locks_[i];
    }

  private:
    std::vector<std::optional<std::mutex>> index_locks_;
    std::mutex instance_lock_;
};

Il convient de mentionner que l'approche "table de hachage" permet très facilement de bloquer ( get_lock (0) suivi de get_lock (16) , par exemple). Cependant, si chaque thread fonctionne sur exactement un élément à la fois, cela ne devrait pas être un problème.

Il existe d'autres compromis avec le verrouillage à grain fin. Les opérations atomiques sont coûteuses, donc un algorithme parallèle qui verrouille chaque élément peut prendre plus de temps que la version séquentielle.

Comment verrouiller efficacement dépend. Les éléments du tableau dépendent-ils d'autres éléments du tableau? Lisez-vous principalement? principalement écrit?

Je ne veux pas diviser le tableau en 8 parties car cela provoquerait un forte probabilité d'attente (l'accès est aléatoire). Les éléments du array est une classe que j'écrirai qui sera codée en plusieurs Golomb valeurs.

Je ne pense pas qu'avoir 8 mutex soit la solution. Si un verrou donné protège une section de tableau, vous ne pouvez pas le changer pour protéger une section différente au milieu d'une exécution parallèle sans introduire une condition de concurrence (rendant le mutex inutile).

Les éléments du tableau sont-ils petits? Si vous pouvez les réduire à 8 octets, vous pouvez déclarer votre classe avec alignas (8) et instancier des objets std::atomic . (La taille dépend de l'architecture. Vérifiez que is_lock_free () renvoie true.) Cela pourrait ouvrir la possibilité d'algorithmes sans verrouillage. Il semble presque qu'une variante des indicateurs de danger serait utile ici. C'est complexe, il est donc probablement préférable d'examiner d'autres approches du parallélisme si le temps est limité.