Thread overview
Multi-Threading LinkedList
November 06

Bu konu 2017'de şurada tartışılmış ve o kadar lezetli ki anlatamam! Türkçe kitaptan alıntılanan ve Ali hoca tarafından geliştirilen bu kod kendini anlatsın... 😀

Hocam izninle, bu leziz kodu biraz (sınıf içine alarak, temsilci kullanarak ve birkaç değişken ismiyle oynayarak) değiştirdim:

import std.conv, std.string, std.stdio;
import core.thread, core.sync.mutex;

shared struct Düğüm
{
  int eleman;
  Düğüm * sonraki;

  size_t length() const
  {
    return 1 + (sonraki ? sonraki.length : 0);
  }

  string toString() const
  {
    string result = to!string(eleman);

    if (sonraki)
    {
      result ~= "\n" ~ to!string(*sonraki);
    }
    return result;
  }
}

shared class Liste
{
  Düğüm * baş;

  void başınaEkle(int eleman)
  {
    baş = new shared(Düğüm)(eleman, baş);
  }

  void ekle(int threadNumarası, Mutex mutex)
  {
    const baş = threadNumarası * elemanAdedi;
    const son = baş + elemanAdedi;

    foreach(sayı; baş .. son)
    {
      {
        scope(exit) mutex.unlock();
        mutex.lock();
        başınaEkle(sayı);
      }
      Thread.sleep(5.msecs);
    }
  }

  string listele() const
  {
    auto result = baş ? to!string(*baş) : "";
    return result.format!"%s";
  }

  size_t length() const
  {
    return baş ? baş.length : 0;
  }
}

enum işParçacığıAdedi = 4;
enum elemanAdedi = 4;

void main()
{
  shared s = new Liste();
  auto mutex = new Mutex();

  Thread[] işçiler;
  foreach(t; 0 .. işParçacığıAdedi)
  {
    /* Orijinali:
    auto işçiYap(int threadNumarası) {
        return new Thread(
         () => s.ekle(threadNumarası, mutex)
       );} /*/
    auto işçiYap(int threadNumarası)
    {
      return new Thread(delegate()
      {
        s.ekle(threadNumarası, mutex);
      });
    } //*/
    işçiler ~= işçiYap(t);
  }

  foreach (işçi; işçiler)
  {
    işçi.start();
  }
  thread_joinAll();
  // İşlerini bitirmelerini bekliyoruz...

  writefln("%s adet eleman olmalı",
            işParçacığıAdedi * elemanAdedi);
  writefln("%s adet eleman var:\n%s",
             s.length, s.listele);
} // araştır: multi threaded circular buffer
November 06
On 11/5/21 10:49 PM, Salih Dincer wrote:

>    size_t length() const
>    {
>      return 1 + (sonraki ? sonraki.length : 0);
>    }

O özyinelemeli işlev yüzünden örneğin 1 milyon kadar az elemanlı liste bile oluşturamadım. Sonunda o işlevi çıkartıp Liste.length diye bir üye ekledim. Ama yalnızca doğruluğunu denetlemek için kullanıldığını görüyorum.

>        Thread.sleep(5.msecs);

Onu çıkarttım.

> enum işParçacığıAdedi = 4;
> enum elemanAdedi = 4;

Onlar için iki farklı değer denedim ve programın çalışmasını ölçtüm. (listele()'yi de çağırmıyorum tabii ki.)

1)

enum işParçacığıAdedi = 1;
enum elemanAdedi = 10_000_000;

$ time ./deneme
10000000 adet eleman olmalı
10000000 adet eleman var

real	0m1.418s
user	0m1.390s
sys	0m0.036s


2)

enum işParçacığıAdedi = 2;
enum elemanAdedi = 5_000_000;

$ time ./deneme
10000000 adet eleman olmalı
10000000 adet eleman var

real	0m5.610s
user	0m6.866s
sys	0m3.488s


On milyon eleman; tek iş parçacığı ile 1.4 saniyede, iki iş parçacığı ile 5.6 saniyede... Ne anladım ben bu işten? ;)

Tabii normalde uzun süren başka işler yaptıklarını düşünürüz ama yine de...

Ali


November 07
On Saturday, 6 November 2021 at 14:18:36 UTC, Ali Çehreli wrote:
> On 11/5/21 10:49 PM, Salih Dincer wrote:
>
> O özyinelemeli işlev yüzünden örneğin 1 milyon kadar az elemanlı liste bile oluşturamadım. Sonunda o işlevi çıkartıp Liste.length diye bir üye ekledim. Ama yalnızca doğruluğunu denetlemek için kullanıldığını görüyorum.

Hiç performans testi yapmamıştım. Şimdi 10 milyon için deneme yapınca Türkçe "Parçalama Hatası" aldım. Sanırım şu ünlü Segmantation Failure? Sende de bu mu oldu hocam?

pico@enpi:~/Belgeler/ufakarsd$ time ./dListMulti_Threading
Hesaplanan ID toplam değeri:484896986
Parçalama arızası

real	0m6,073s
user	0m6,395s
sys	0m8,364s

November 07
On 11/7/21 1:59 AM, Salih Dincer wrote:

> Hiç performans testi yapmamıştım.

O açıdan değerli bir program olmuş. ;)

> Şimdi 10 milyon için deneme yapınca
> Türkçe "Parçalama Hatası" aldım. Sanırım şu ünlü Segmantation Failure?
> Sende de bu mu oldu hocam?

Evet. O, length() işlevi yüzünden oluyor: Özyinelemeli olduğundan 10 milyon kere çağırmaya çalışıyoruz. (Zaten o yüzden delice de yavaştır: Uzunluk öğreneceğiz diye eleman adedi kadar çağrı yapıyoruz. (Yani O(N). Olmaz. :) )) Sonuçta da "program stack"e sığmıyoruz.

Ali


November 08

On Sunday, 7 November 2021 at 14:41:16 UTC, Ali Çehreli wrote:

>

O açıdan değerli bir program olmuş. ;)

Hocam asıl değerli olan şu Linked List'i icad etmek! Eskiden de konuşuyorduk (sanırım yıl 2012 idi) ben o zamanlar şimdiki kadar değerini bilemedim.

>

Evet. O, length() işlevi yüzünden oluyor: Özyinelemeli olduğundan 10 milyon kere çağırmaya çalışıyoruz. (Zaten o yüzden delice de yavaştır: Uzunluk öğreneceğiz diye eleman adedi kadar çağrı yapıyoruz. Yani O(N). Olmaz. :)

Uç uca bağlama yöntemini ters şekilde yapınca parçalama hatası düzeldi. Çünkü burada paylaştığım örnek koddaki "Düğüm * sonraki" bence önceki. Bunu ancak kodla anlatabilirim...

Düğümleri saran şöyle basit bir sınıfımız olsun:

class List(T) {
  struct Node {
    T item;
    Node* next;
  }

  Node* root, iter;

  this(T item = T.init) {
    iter = new Node(item, null);
    root = iter;
  }
//...

Eğer her yeni düğümü iter = new Node(item, iter); olacak şekilde üretirsek (lütfen hayal edin) aşağıdan yukarıya doğru uzanan bir kule gibi birleştirilmiş oluyor. Oysa şu boş bir root fazlalığı dışında (onun da yararı var hatta zincir yapıp sayısı arttırılabilir) hatasız çalıştığını gördüm. Yani şöyle:

  void insertFront(T item) {
    (*iter).next = new Node(item, null);
    this.Next;
  }

  void goFront() {
    iter = root;
  }

  auto Next() {
    return iter = iter.next;
  }

Düğümleri bir döngü içinde oluşturduktan sonra goFront() yapıp basit bir do while(Next) ile çok hızlı düğümler arası gezdim. Harikaydı!

  size_t n;
  do {
    n += list.Get;
  } while(list.Next);
  n.writeln;
November 09
On 11/8/21 12:41 PM, Salih Dincer wrote:

> Hocam asıl değerli olan şu Linked List'i icad etmek! Eskiden de
> konuşuyorduk (sanırım yıl 2012 idi) ben o zamanlar şimdiki kadar
> değerini bilemedim.

Linked list eğlencelidir ve işe giriş mülakatlarında çok çıkar ama gerçekte hemen hemen hiç kullanılmaz. Ben bağlı listenin diziden daha uygun olduğu problemle karşılaşmadım. Olsa olsa, belleğin sonuna gelmişizdir de dizinin büyümek için istediği kadar bellek kalmamıştır... Belki öyle bir uç durumda bağlı liste şanslı olabilir. Onun dışında hiçbir konuda üstünlüğü yoktur. :)

* Daha fazla bellek harcar

* Elemanlara erişimi daha masraflıdır

* Rasgele erişim sağlayamaz

* CPU iç belleğinin yardımlarından yararlanamaz

* vs.

Listeden belirli bir elemanı çıkartma konusunda diziden hızlı görünür ama o durumda bile listenin amacına bağlı olarak o eleman "geçersiz" olarak işaretlenebilir veya dizinin en sonundaki eleman çıkan elemanın yerine gelebilir (evet, o zaman sıra bozulur).

Evet, işin gerçeği o. :)

> çok hızlı düğümler arası gezdim. Harikaydı!

Dizi kadar hızlı olamaz. :)

Ali


November 11
On Tuesday, 9 November 2021 at 18:45:34 UTC, Ali Çehreli wrote:
> Dizi kadar hızlı olamaz. :)
>
> Ali

Elbette sıralı okuma ile yarışamaz ama listeyi bölme ve/veya içinden eleman çıkarma/taşıma vb. işlemleri (sıralama algoritmaları) avantajlı oluyor. İşte bu potansiyel benim çok ilgimi çekiyor.
November 11
On 11/11/21 10:27 AM, Salih Dincer wrote:
> On Tuesday, 9 November 2021 at 18:45:34 UTC, Ali Çehreli wrote:
>> Dizi kadar hızlı olamaz. :)
>>
>> Ali
>
> Elbette sıralı okuma ile yarışamaz ama listeyi bölme ve/veya içinden
> eleman çıkarma/taşıma vb. işlemleri (sıralama algoritmaları) avantajlı
> oluyor. İşte bu potansiyel benim çok ilgimi çekiyor.

Bağlı listenin daha uygun olduğu durum olabilir ama dediğim gibi, pratikte hemen hemen hiç karşılaşılmaz. Sen bir örnek düşünebilir misin? Ben yukarıda gösterdiğin her işlemde dizinin daha hızlı olacağını düşünüyorum.

Bunun örnekleri gösterilmiştir. Bjarne Stroustrup'un bir videosunu buldum:

  https://www.youtube.com/watch?v=YQs6IC-vgmo

Oradaki örnek şu: Tamsayılar gelecek; sıralı olarak tutacağız; ve sonra rasgele eleman çıkartacağız. Dizi mi hızlıdır, liste mi? Aynı konuda yazılar da görmüştüm. Tabii herkes kendi denemesini de yapabilir. ;)

Ali


November 12

On Thursday, 11 November 2021 at 21:29:41 UTC, Ali Çehreli wrote:

>

On 11/11/21 10:27 AM, Salih Dincer wrote:

>

On Tuesday, 9 November 2021 at 18:45:34 UTC, Ali Çehreli
wrote:

>

Dizi kadar hızlı olamaz. :)

Ali

Elbette sıralı okuma ile yarışamaz ama listeyi bölme ve/veya
içinden
eleman çıkarma/taşıma vb. işlemleri (sıralama algoritmaları)
avantajlı
oluyor. İşte bu potansiyel benim çok ilgimi çekiyor.

Bağlı listenin daha uygun olduğu durum olabilir ama dediğim gibi, pratikte hemen hemen hiç karşılaşılmaz. Sen bir örnek düşünebilir misin?

Aslında aklımda gerçek hayattan güzel bir örnek var: Sequencer (SIRALAYICI) ve bunu bugün hazır kod (sadece veri kısmı) olarak ayrı bir başlık altında paylaşacağım ama önce basit bir çerçeve belirleyelim:

50 birimlik (materialHand) bölmeniz (container) var ve bu bölme malzemelerin bırakıldığı yerin (mFeeder) altında (örn. Soldan Sağa) doğru kayıyor...

Örneğin 5 adet malzemeniz var ve bunlar (feeder'lar) rasgele olarak 50 birimlik alanın üstünde hazırda baklemekte ve en soldaki malzemeden başlamak kaydıyla malzeme beslemesi yapıyor...

Her 10 ms.'de kayma (shifting) yapıyor ve sondaki malzeme montaj alanına giden banda aralıklı (aşağıda görülmeyen 57. satır) düşüyor. Sıralama (program) şu şekide:

  • 13 numaralı malzeme 3 adet (1, 2, 3)

  • 1 numaralı malzeme 3 adet (4, 5, 6)

  • 13 numaralı malzeme 3 adet (7, 8, 9)

  • 1 numaralı malzeme 3 adet (10, 11, 12)

  • 23 numaralı malzeme 2 adet (13, 14)

  • 46 numaralı malzeme 2 adet (15, 16)

  • 13 numaralı malzeme 1 adet (17)

  • 45 numaralı malzeme 2 adet (18, 19)

  • 23 numaralı malzeme 2 adet (20, 21)

  • 46 numaralı malzeme 2 adet (22, 23)

  • 13 numaralı malzeme 1 adet (24)

  • 45 numaralı malzeme 2 adet (25, 26)

  • 23 numaralı malzeme 2 adet (27, 28)

  • 46 numaralı malzeme 2 adet (29, 30)

  • 13 numaralı malzeme 1 adet (31)

  • 45 numaralı malzeme 4 adet (32, 33, 34, 35)

  • 13 numaralı malzeme 1 adet (36)

  • 46 numaralı malzeme 2 adet (37, 38)

  • 23 numaralı malzeme 2 adet (39, 40)

  • 45 numaralı malzeme 2 adet (41, 42)

  • 13 numaralı malzeme 1 adet (43)

  • 46 numaralı malzeme 2 adet (44, 45)

  • 23 numaralı malzeme 2 adet (45, 47)

  • 45 numaralı malzeme 2 adet (48, 49)

  • 13 numaralı malzeme 1 adet (50)

  • 46 numaralı malzeme 2 adet (51, 52)

  • 23 numaralı malzeme 2 adet (53, 54)

  • 45 numaralı malzeme 2 adet (55, 56)

Bu simetrik 56 satırlık program elbette bloklara bölüp sadeleştirilebilir ama gelen verinin böyle sıralı (2 x 56) geldiğini ve 57 satırın boşluk yani bir sonraki üretilen (örn. elektrikli süpürge) olduğunu varsayarsak. Malzemeleri veren bölüm ise şöyle eşleştirilebilir:

  • material = 1, feeder = 6
  • material = 13, feeder = 19
  • material = 23, feeder = 13
  • material = 45, feeder = 3
  • material = 46, feeder = 26

Malzemelerin isimleri rasgele (elma, armut, karpuz vb.) olabilir ama gerçek hayattaki bir üretim bandını temsil etmesi açısından sırasıyla:

  • kablo
  • lamba
  • parça (plastik)
  • vida1 (alüminyum)
  • vida2 (demir)

Sorularınız olursa burada paylaşın, ben cevabı kodlar içinde vereceğim. Hatta bu spawn() ile yapılabilir çünkü dizilime göre aynı anda 2 feeder (belki 3!) çalışıp container'ın ilgili bölmesine malzemeyi bırakır.

Dolayısıyla gerçek hayatta işleyen bu otomasyon bandı zorlayıcı bir örnek olabilir. Bence Array de LinkedList de avantajlı. Belki composite bir çözüm akıllıca olabilir?

Sevgiler, saygılar...