czemu linked listy są powszechnie implementowane na wskaźnikach, a nie na tablicach?

mój mental model aż do niedawna:

• struktury tablicowe (tablice, wektory, kopce, itp) są, co do stałej, wydajne
• struktury wskaźnikowe (drzewa, linked listy, itp) są, co do stałej, prostytutkowo niewydajne

powód jest taki: gdy wszystko jest w tablicy, to wszystkie elemnty tablicy będa trzymane w pamięci obok siebie
ale gdy mamy strukturę wskaźnikową, to poszczególne elementy mogą być od siebie dowolnie daleko
np załóżmy że mamy linked list na wskaźnikach. Mamy element pierwszy, dajmy na to pod adresem 0x12345678. Teraz dodajemy drugi element, wołamy jakieś new czy inne malloc, ten element otrzymuje adres 0x87654321. Linked lista obok elementu pierwszego przechowuje wskaźnik na element drugi. Iterowanie po linked liście to jest O(1), ale problem polega na tym, że przejście z 0x12345678 do 0x87654321 to niemal gwarantowany cache miss, więc procek nic nie robi, tylko czeka na pobranie kolejnej strony.
tymczasem gdybyśmy mieli tablicę to elementy są obok siebie i żyją sobie na jednej stronie. Gdy pobieramy jeden element to automatycznie pobieramy całą stronę więc pobranie elementu drugiego jest natychmiastowe, bo wszystkie już są w cache.

Różnica między linked listami a tablicami (co do złożoności asymptotycznej) jest taka:

• Pobranie ntego elementu w linked liście to O(n), tymczasem w tablicy to O(1)
• Ale gdy już jesteśmy przy n-tym elemencie, to usunięcie tegoż n-tego elementu albo wstawienie nowego elementu pomiędzy n-tym a (n+1)szym to w linked liście O(1), podczas gdy w tablicy to O(n)
• Bazując na linked listach można zaimplementować w pełni funkcyjną listę (pozwalającą na dodanie / usunięcie elementu bez mutowania) w O(1), podczas gdy w tablicach jest to O(n) (kopiowanie całej tablicy)

Dlatego ogólne zalecenie jest takie: o ile możemy uzywamy tablic, linked list tylko o ile musimy (jeśli NAPRAWDĘ potrzebujemy wstawiać / usuwać elementy ze środka listy w O(1) albo jesteśmy fanatykami FP i nie akceptujemy żadneog mutowania za żadne skarby świata) -- ale musimy pamiętac, że tak czyniąc będziemy rozrzucać dane po pamięci, więc ilość cache misses będzie szła pod orbitę, więc nie wolno nam tak postąpić, jeśli lista jest w jakiejś tight loop i wydajność samej listy zaczyna być wąskim gardłem (co może się zdarzyc przy algorytmach / implementacji AI / obliczeniach naukowych / itp, ale raczej nie przy "normalnym" klepaniu).

==================================

@Autysta i @Czitels zachwieli tym moim mental model:

Zamiast implementować double linked list w C++ na pointerach to będziesz implementował na indexach tablicy w rust. — Autysta 2024-02-08 21:34
Zamiast mieć pointer do następnego elementu to masz index do miejsca w tablicy gdzie jest następny element inaczej tego w Rust nie napiszesz, bo język cię będzie ograniczał. — Autysta 2024-02-08 22:15
@YetAnohterone: możnaby stworzyć strukturę która by przechowywała index i wartość a obiekty tej struktury byłyby elementami tablicy. Iterowanie byłoby po pętli, ale still da się to zrobić xd, tylko wszystkie operacje byłyby bardzo brzydkie. — Czitels 2024-02-09 00:46

(źródło: https://4programmers.net/Forum/C_i_C++/371797-kosci_wracaja_do_c?p=1949512#comment-957228)

To było tak sprzeczne z moim powyższym mental model, że w pierwszym odruchu po prostu na ślepo zaprzeczyłem. Przecież jeśli da się zaimplementować linked listę na tablicy (gdzie "linked lista" to lista umożliwiająca dodawanie/usuwanie elementów ze środka w O(1) i tym podobne gwarancje asymptotycznej złożoności zwyczajowo kojarzone z linked listami), no to spada nam główna i podstawowa bolączka związana z linked listami, czyli ich wrogość dla cache procesora i stąd wynikająca prostytutkowo duża stała przy pobieraniu każdego kolejnego elementu. Zatem nie ma żadnego sensu implementować linked list na wskaźnikach, należy je implementować tylko na tablicach. Tymczasem o ile mi wiadomo wszystkie bilbioteki standardowe implementują linked listy na wskaźnikach właśnie: w C++ std::list jest strukturą wskaźnikową, w C# Systems.Collections.Generic.LinkedList jest strukturą wskaźnikową, w Haskellu domyślnie wszystkie listy i stringi są strutkurami wskaźnikowymi (to są pod spodem po prostu linked listy) by zapewnić pełną funkcyjność (stąd wypływa ich niska wydajność i konieczność przejścia do z natury bardziej imperatywnych tablic, gdy wydjaność zaczyna byuć potrzebna (koci mi się niejasno, że gdzieś się po hackage wala imperatywna, mutowalna tablica do użycia w takich wypadkach), w Ruście std::collections::LinkedList jest strukturą wskaźnikową (i dlatego oficjalna dokumentacja https://doc.rust-lang.org/std/collections/struct.LinkedList.html zaleca użycie tablic gdzie tylko jest to mozliwe właśnie z powodu działania cache procesora), itp, itd). Tak więc implementacja linked listy na tablicy nie może być możliwa, bo gdyby była możliwa, to z pewnością bilbioteki standardowe Rusta, C++, C#, Haskella i innych implementwały je dla wydajności właśnie na tbalicach, a nie na wskaźnikach, jak to czynią.

Po zastanowieniu wydaje mi sie, że to jednak @Czitels i @Autysta mieli rację - chyba istotnie jak najbradziej można zrobić ilnked listę na tablicy, nie trzeba tylko i wyłącznie na wskaźnikach.

Ale w takim razie czemu biblioteki standardowe chyba wszystkich języków implementują linked listy na wskaźnikach, biorąc pod uwagę, że wszelkie wskaźnikowe struktury danych z automatu będą musiały być prostytutkowo niewydajne ze względu na ciągłe cache misses?

Linked lista przydaje się, gdy rzadko czytasz a często modyfikujesz. Dobre przykłady:

• instrusive kolekcje tj. https://www.boost.org/doc/libs/1_79_0/doc/html/intrusive/intrusive_vs_nontrusive.html . Polecam przeczytać ten link
• wielowątkowe modyfikacje np. słynne https://en.wikipedia.org/wiki/Read-copy-update w jądrze linuxa

Taka opakowana kolekcja jak std::list w C++ praktycznie rzadko się przydaje, bo nie ma zalety intrusive linked listy. W normalnym jednowątkowym kodzie linked lista przydaje się bardzo rzadko

YetAnohterone napisał(a):

To było tak sprzeczne z moim powyższym mental model, że w pierwszym odruchu po prostu na ślepo zaprzeczyłem. Przecież jeśli da się zaimplementować linked listę na tablicy (gdzie "linked lista" to lista umożliwiająca dodawanie/usuwanie elementów ze środka w O(1) i tym podobne gwarancje asymptotycznej złożoności zwyczajowo kojarzone z linked listami), no to spada nam główna i podstawowa bolączka związana z linked listami, czyli ich wrogość dla cache procesora i stąd wynikająca prostytutkowo duża stała przy pobieraniu każdego kolejnego elementu. Zatem nie ma żadnego sensu implementować linked list na wskaźnikach, należy je implementować tylko na tablicach.

Ale przecież nie wiesz, że ten kolejny element jest obok. No chyba, że przy wstawianiu będziesz układał odpowiednio elementy całej kolekcji. Nie będzie to ani O(1) i w ogóle wyjdzie z tego coś, co nie jest linkedlistą.
A inicjalnie, to jak rozumiem chcesz alokować pod taką strukturę całą pamięć maszyny? Bo w przeciwnym razie przy którymś wstawieniu będziesz musiał "doalokowywać" więcej pamięci, a to też nie będzie O(1).

w C# Systems.Collections.Generic.LinkedList jest strukturą wskaźnikową

Aż spojrzałem do kodu: https://github.com/microsoft/referencesource/blob/master/System/compmod/system/collections/generic/linkedlist.cs i jakoś ani jednego wskaźnika nie zobaczyłem.

somekind napisał(a):

Ale przecież nie wiesz, że ten kolejny element jest obok. No chyba, że przy wstawianiu będziesz układał odpowiednio elementy całej kolekcji. Nie będzie to ani O(1) i w ogóle wyjdzie z tego coś, co nie jest linkedlistą.

nie trzeba układać elementów całej kolekcji, wystarczy przy każdym elemencie trzymać indeks następnego. Wyjdzie O(1). Co prawda elementy takiej listy będą porozrzucane po kolekcij, ale to o niebo lepiej, niż porozrzucanie elementów listy po całej pamięci. Głupia implementacja takiej 'linked listy' poniżej.

A inicjalnie, to jak rozumiem chcesz alokować pod taką strukturę całą pamięć maszyny? Bo w przeciwnym razie przy którymś wstawieniu będziesz musiał "doalokowywać" więcej pamięci, a to też nie będzie O(1).

będzie zamortyzowane O(1).

Aż spojrzałem do kodu: https://github.com/microsoft/referencesource/blob/master/System/compmod/system/collections/generic/linkedlist.cs i jakoś ani jednego wskaźnika nie zobaczyłem.

dobrze, ok, w c# będziemy mieli tam referencje, a nie wskąxniki, tym niemniej w c# referencje są implementowane jako wskaźniki. z punktu widzenia pamięci komputera mamy strukturę wskaźnikową, a w tym wypadku liczy się niski poziom, a nie konstrukcje wysokopoziomowego języka programowania. Pisałem o sytuacji w kilku językach i wydaje mi się, że użyte przeze mnie słowo 'wskaźnik' miało klarowne znaczenie, nawet jeśłi nie do końca ściśle odpowiada nomenklaturze poszczególnych języków wysokopoziomowych.

========================

Głupia implementacja linked listy na tablicy poniżej (C#). Tak wiem, kod ma wady i nie jest najpiękniejszy, ale nie o to tu chodzi tylko o proof of concept do implementacji struktury danych.

using System.Collections.Generic;

#nullable enable

public class MyLinkedList<T>
{
	private record struct MyLinkedListNode (int? prev, int? next, T elt);
	
	private List<MyLinkedListNode> backingArr = new();
	
	private int? first = null, last = null, curr = null;
	
	public T? First => 
		first is int f ?
		backingArr[f].elt :
		default(T);
	
	public T? Last =>
		last is int l ?
		backingArr[l].elt :
		default(T);
	
	public T? Current =>
		curr is int c ?
		backingArr[c].elt :
		default(T);
	
	public T? Next()
	{
		if(curr is int c && backingArr[c].next is int n)
		{
			curr = n;
			return Current;
		}
		else
		{
			return default(T);
		}
	}
	
	public T? Prev()
	{
		if(curr is int c && backingArr[c].prev is int p)
		{
			curr = p;
			return Current;
		}
		else
		{
			return default(T);
		}
	}
	
	private int Add(int? prev, int? next, T val)
	{
		int i = backingArr.Count;
		backingArr.Add(new MyLinkedListNode(prev, next, val));
		
		if(curr is null)
			curr = i;
		
		return i;
	}
	
	public void AddFirst(T val)
	{
		int newFirst = Add(null, first, val);
		
		if(first is int f)
			backingArr[f] = backingArr[f] with {prev = newFirst};
			
		first = newFirst;
	}
	
	public void AddLast(T val)
	{
		int newLast = Add(last, null, val);
		
		if(last is int l)
			backingArr[l] = backingArr[l] with {next = newLast};
		
		last = newLast;
	}
	
	public void AddAfter(T val)
	{
		if(curr == last)
		{
			AddLast(val);
		}
		else // zatem lista nie jest pusta, bo inaczej byłoby curr == last == null
		{
			int c = curr!.Value;
			int newNext = Add(c, backingArr[c].next, val);
			int oldNext = backingArr[c].next!.Value;
			backingArr[c] = backingArr[c] with {next = newNext};
			backingArr[oldNext] = backingArr[oldNext] with {prev = c};
		}
	}
	
	public void AddBefore(T val)
	{
		if(curr == first)
		{
			AddFirst(val);
		}
		else // zatem lista nie jest pusta, bo inaczej byłoby curr == first == null
		{
			Prev();
			AddAfter(val);
			Next(); Next();
		}
	}
	
	private void Delete(int i)
	{
		if(i == curr)
			curr = null;
		
		if(i == first)
			first = backingArr[i].next;
		
		if(i == last)
			last = backingArr[i].prev;
		
		if(backingArr[i].prev is int p)
			backingArr[p] = backingArr[p] with {next = backingArr[i].next};
		
		if(backingArr[i].next is int n)
			backingArr[n] = backingArr[n] with {prev = backingArr[i].prev};
		
		if(i != backingArr.Count-1)
		{
			backingArr[i] = backingArr[backingArr.Count-1];
			
			if(backingArr.Count-1 == curr)
				curr = i;
			
			if(backingArr.Count-1 == first)
				first = i;
			
			if(backingArr.Count-1 == last)
				last = i;
			
			if(backingArr[i].prev is int prev)
				backingArr[prev] = backingArr[prev] with {next = i};
			
			if(backingArr[i].next is int next)
				backingArr[next] = backingArr[next] with {prev = i};
		}
		
		backingArr.RemoveAt(backingArr.Count-1);
	}
	
	public void DeleteFirst()
	{
		if(first is int f)
			Delete(f);
	}
	
	public void DeleteLast()
	{
		if(last is int l)
			Delete(l);
	}
	
	public void DeleteAfter()
	{
		if(curr is int c && backingArr[c].next is int n)
			Delete(n);
	}
	
	public void DeleteBefore()
	{
		if(curr is int c && backingArr[c].prev is int p)
			Delete(p);
	}
}

YetAnohterone napisał(a):

mój mental model aż do niedawna:

• struktury tablicowe (tablice, wektory, kopce, itp) są, co do stałej, wydajne
• struktury wskaźnikowe (drzewa, linked listy, itp) są, co do stałej, prostytutkowo niewydajne

powód jest taki: gdy wszystko jest w tablicy, to wszystkie elemnty tablicy będa trzymane w pamięci obok siebie
ale gdy mamy strukturę wskaźnikową, to poszczególne elementy mogą być od siebie dowolnie daleko
np załóżmy że mamy linked list na wskaźnikach. Mamy element pierwszy, dajmy na to pod adresem 0x12345678. Teraz dodajemy drugi element, wołamy jakieś new czy inne malloc, ten element otrzymuje adres 0x87654321. Linked lista obok elementu pierwszego przechowuje wskaźnik na element drugi. Iterowanie po linked liście to jest O(1), ale problem polega na tym, że przejście z 0x12345678 do 0x87654321 to niemal gwarantowany cache miss, więc procek nic nie robi, tylko czeka na pobranie kolejnej strony.
tymczasem gdybyśmy mieli tablicę to elementy są obok siebie i żyją sobie na jednej stronie. Gdy pobieramy jeden element to automatycznie pobieramy całą stronę więc pobranie elementu drugiego jest natychmiastowe, bo wszystkie już są w cache.

Jest oddzielna strona pamięci do sterty i stosu.
Łatwo można sprawdzić w cat /proc/PID/maps strony pamięci, odwołanie się pod adres, który nie należy do strony z tego zakresu tych stron skutkuje segfaultem.

Alokacja na stercie jest zawsze robiona na tej samej stronie od sterty, wyjątek jest jak się przekroczy rozmiar 4KB to wtedy następna jest dociągana od systemu.
Elementy leżą jeden obok drugiego na stercie, wyjątek jest jak zacznie się robić usuwanie i inne struktury będą także alokować inne dane to wtedy się zrobi taka fragmentaryzacja.

Operowanie na wskaźnikach niczym nie różni się od tablic tu i tu jest pamięć.
Różnica taka, że na heapie obiety uzyskane przez new są opakowane w dodatkowe struktury.
Przykładowo jeśli zaalokuje inta 4 bajty to padding wyrówna mi go do 8 bajtów, bo to najmniejsze słowo na jakim działa cache.
Dodatkowe 2 inty wychodzą w skład struktury, która określa ile bajtów zostało zaalokowanych lub i czasem w niektórych implementacjach ile bajtów wyżej jest element wcześniej.
Czyli razem 16 bajtów przy alokacji 4 bajtów inta zużyjesz.
Czyli heap jest na takiej liście zbudowany.

Przez co element obok elementu będzie jeśli nic między nimi nie było alokowane i jedynie metadane bloku będą wchodziły w paradę.
W tablicy upchniesz jeśli każdy element będzie miał 1 inta, 16 intów w cache line, a na heapie to wyjdzie alokując po jednym 4, przez to że bloki metadanych są zawsze o 0x8 nad samym elementem alokowanym w pamięci.
Może też być inny sposób alokowania na heapie bez takiego bloku metadanych to wtedy niczym by się nie różniło od zwykłej tablicy.
Czyli jakbyśmy zrobili na tablicy to byśmy musieli jakiś sposób zarządzania pamięcią wymyśleć, C/C++ używa metabloków na heapie, opakowuje zaalokowany element w kolejną strukturę, która jest niczym innym jak dodaniem tylko 8 bajtów metadanych.
Można też bez takich bloków zrobić wtedy trzeba inną strukturę dać, która będzie przechowywać informacje o zajętych blokach np. następna tablica, tak żeby ta pierwsza mogła być continious.

Z drugiej strony jak to aplikacja działa na wielu rdzeniach.
To nawet lepiej jak każdy element mieści się tylko i wyłącznie do jednego cache line gdyż jak inny rdzeń zmodyfikuje cache line to wszystkie rdzenie, które także z tego korzystały to także muszą zsynchronizować dane, a jeśli dane nie leżą w tym samym cache line to nie trzeba tej synchronizacji wykonywać i jest szybciej.

@Autysta i @Czitels zachwieli tym moim mental model:

Dla mnie wszystko jest matematycznym modelem, a implementacja to tylko szczegół, który może być zrealizowany na wiele sposobów.

Żeby było śmieszniej, to Lista na wskaźnikach jest implementowana na liście na tablicach, bo malloc używa implementacji heapu jako lista tablicowa.

somekind napisał(a):

YetAnohterone napisał(a):

To było tak sprzeczne z moim powyższym mental model, że w pierwszym odruchu po prostu na ślepo zaprzeczyłem. Przecież jeśli da się zaimplementować linked listę na tablicy (gdzie "linked lista" to lista umożliwiająca dodawanie/usuwanie elementów ze środka w O(1) i tym podobne gwarancje asymptotycznej złożoności zwyczajowo kojarzone z linked listami), no to spada nam główna i podstawowa bolączka związana z linked listami, czyli ich wrogość dla cache procesora i stąd wynikająca prostytutkowo duża stała przy pobieraniu każdego kolejnego elementu. Zatem nie ma żadnego sensu implementować linked list na wskaźnikach, należy je implementować tylko na tablicach.

Ale przecież nie wiesz, że ten kolejny element jest obok. No chyba, że przy wstawianiu będziesz układał odpowiednio elementy całej kolekcji. Nie będzie to ani O(1) i w ogóle wyjdzie z tego coś, co nie jest linkedlistą.
A inicjalnie, to jak rozumiem chcesz alokować pod taką strukturę całą pamięć maszyny? Bo w przeciwnym razie przy którymś wstawieniu będziesz musiał "doalokowywać" więcej pamięci, a to też nie będzie O(1).

w C# Systems.Collections.Generic.LinkedList jest strukturą wskaźnikową

Aż spojrzałem do kodu: https://github.com/microsoft/referencesource/blob/master/System/compmod/system/collections/generic/linkedlist.cs i jakoś ani jednego wskaźnika nie zobaczyłem.

wtf? a czym jest LinkedListNode?

@YetAnohterone

Chyba ślepy jestem i nie widzę abyś poruszał tę kwestię, ale ile dzieje się operacji w tej linijce?

backingArr.Add(new MyLinkedListNode(prev, next, val));

a w szczególności w metodzie Add?

No bo imo to jest ta różnica w praktyce o którą pytasz

@YetAnohterone przy próbie 'usprawniania' list łączonych trzeba wziąć pod uwagę pewne rzeczy:

• w typowym kodzie (biznesowym czy nie) prawie wszystkie mutowalne listy są oparte o tablice, tzn. programiści wprost wybierają array listy, bo przewagi list łączonych są prawie zawsze zbędne, a przewagi list tablicowych są prawie zawsze przydatne
• jeśli chcesz stworzyć listę łączoną ogólnego przeznaczenia opartą o tablicę to najpierw musisz zrobić jakieś rozpoznanie potencjalnych przypadków użycia, tzn. przejrzeć faktyczne projekty i przeanalizować czy taka lista jest w nich potrzebna, a jeśli jest to jaką ma mieć charakterystykę wydajnościową i pamięciową (w rozbiciu tejże charakterystyki na poszczególne operacje)
• jeśli tablica w tej twojej liście łączonej odpowiednio dużo urośnie to będziesz i tak miał cache misses ciągle (przy założeniu, że elementy są losowo porozrzucane po tej tablicy)
• używana pod spodem lista tablicowa ma metody add i delete(koniec), które mają zamortyzowaną złożoność O(1), ale co jakiś czas masz zmianę rozmiaru tablicy pod spodem i to trwa O(n) - to może być nieakceptowalne, tzn. ktoś może wybrać listę łączoną właśnie po to, by uniknąć takiego rozszerzania czy zmniejszania tablicy pod spodem
• region-based moving GC (np. https://en.wikipedia.org/wiki/Garbage-first_collector , zgc, shenandoah i mniej oficjalne gc w javie) podczas przechodzenia przez zwykłą listę łączoną przenosi ją w nowy region w liniowym ułożeniu (tzn. w kolejności przechodzenia przez listę) przez co kod aplikacyjny przechodzący przez taka listę nie będzie latał za losowymi wskaźnikami tylko de facto skanował pamięć liniowo
• w niemutowalnych listach łączonych, w przypadku programowania funkcyjnego, bardzo ważna jest złożoność obcinania głowy listy oraz dodawania nowej głowy - obie operacje powinny trwać O(1). ponadto niemutowalne oznacza niemutowalne (sic!), a więc stara kopia powinna zostać niezmieniona (tzn. nie powinno dać się zaobserwować zmian w starej kopii).
• mimo wszystko twoja implementacja listy łączonej może mieć sens, ale o zdanie trzeba pytać użytkowników list łączonych, bo biblioteka standardowa nie jest przeznaczona dla przypadkowych odkrywców hobbystów, a raczej jest podwaliną komercyjnych czy szeroko używanych aplikacji. obstawiam, że tak gruntowna zmiana implementacji łączonej nie wchodzi w grę (zbyt dużo zmian charakterystyki wydajnościowej i pamięciowej, nie zawsze na lepsze). co najwyżej mógłbyś dodać nową klasę do biblioteki standardowej.

czemu linked listy są powszechnie implementowane na wskaźnikach, a nie na tablicach?

Bo z założenia lista łączona rozwiązuje inny problem niż tablica, a konkretnie ma zapewnić stabilność wskaźników przy dodawaniu i usuwaniu. Jak potrzebujesz efektywnego przeszukiwania to wybierasz inny kontener.

W praktyce rzadko kiedy potrzebuje się typowej listy łączonej i tak na szybko jestem w stanie sobie przypomnieć tylko jedno praktyczne zastosowanie w postaci free_list w arena alokatorach. Dlatego często widuje się hybrydowe implementacje, np. bucket array albo listy łączone używające ciągłego prealokowanego obszaru pamięci itp. Wszystko w zależności jaki problem musisz rozwiązać.

@YetAnohterone:

a) Nie kumam czym mentalnie się różni niskopoziomowy wskaźnik od indeksu do następnego (oprócz mnożenia i dodawania ofsetu) i dlaczego jedno by było O(1) a drugie nie

b) na wskaźnikach jest Turing-complete (da się w pełni zrealizować temat) a na tablicach nie, trzeba robić jakieś hacki na przypadki szczególne np przepełnienie - czyli wychodzić z czystego ujęcia "widzę tablicę"

c) mityczna przyjazność dla cache tablic jest przereklamowana (za dużo zależy od warunków z gwiazdką u dołu). Będzie oczywista dla niewielkich tablic na typach prostych / przez wartość else wcale nie tak bardzo

Zgaduję, że KISS. Po co komplikować implementację, która miałaby optymalizować coś w warstwach, na których nie masz kontroli nad kluczowymi elementami:

a) sposobem w jaki linked lista będzie wykorzystywana przez kogoś
b) workloadami, które będą konkurować o zasoby (czy to CPU, czy cache L1..L3, TLB, page cache itp.)
c) modelem pamięci maszyny wirtualnej (o ile używasz jakiejś maszyny wirtualnej)

Przykładowo jeśli zaalokuje inta 4 bajty to padding wyrówna mi go do 8 bajtów, bo to najmniejsze słowo na jakim działa cache.
Dodatkowe 2 inty wychodzą w skład struktury, która określa ile bajtów zostało zaalokowanych lub i czasem w niektórych implementacjach ile bajtów wyżej jest element wcześniej.
Czyli razem 16 bajtów przy alokacji 4 bajtów inta zużyjesz.

Nie, to w ogólności nie jest prawdą. Może to jest prawda w językach OOP gdzie obiekty mają nagłówki, wskaźnik do vtable, pola używane przez GC itp. W takim C jak zaalokujesz 4B to możesz dostać 4B i nie ma żadnych nagłówków ani paddingu. Padding jest kwestią implementacji konkretnego alokatora. Jeśli chodzi o samo CPU to większość CPU dopuszcza dostęp bez wyrównania. Alokator nie musi pamiętać długości chunka dla każdego chunka z osobna. Długość chunka może znaleźć na podstawie adresu.

@Krolik widzę, że nie masz pojęcia o czym gadasz, no tak kompilator wyrównuje za nas, tak w cpu można za pomocą operacji mov pobrać bajt, word, dword qword, ale cache nie pobiera w takich wielkościach, te wyrównania się stosuje, a przynajmniej kompilator je stosuje bo tacy ludzie jak ty nie rozumieją do czego to jest potrzebne, w sumie to nikt tutaj na forum nie rozumie.

A c**** niech stracę.
Wyobraź sobie, że masz dwie tablice a i b.
Jedna tablica to jest jeden cacheline i wyobraź sobie, że int leży 2 bajty w jednej tablicy i 2 bajty w drugiej, to musisz odwołać się do dwóch oddzielnych cachelinów i potem splitnąć do jednego rejestru, a normalnie jak jest wyrównane to zawsze rejestr się odwołuje do jednego cacheline.

Krolik napisał(a):

W takim C jak zaalokujesz 4B to możesz dostać 4B i nie ma żadnych nagłówków ani paddingu.

Lepiej wróć do javascript, jak sprawdzisz sizeof(int) to tak dostaniesz wartość 4, tak samo jak to zrobisz na adresie na który dasz typ int, jak zrobisz rzutowanie to zmienisz tą wielkość, np. rzutujesz na char to będzie teraz 1 bajt.
A jak sprawdzisz jak to robi malloc heap alokator.
To zobaczysz, że akurat ta wersja domyślna na gcc opakowuje każde zaalkowane bajty w strukturę, która zawiera ile bajtów jest w danym bloku.

Wyjasnienie napisał(a):

Jedna tablica to jest jeden cacheline i wyobraź sobie, że int leży 2 bajty w jednej tablicy i 2 bajty w drugiej, to musisz odwołać się do dwóch oddzielnych cachelinów i potem splitnąć do jednego rejestru, a normalnie jak jest wyrównane to zawsze rejestr się odwołuje do jednego cacheline.

Cacheline to tylko optymalizacja. Do tego mylisz pojęcia. Cacheline jest używany tylko, gdy czytamy dane. Jak zaalokuję milion intów a potem nic z nimi nie robię to czy mam cacheline czy nie i tak będę miał tą samą ilość pamięci zaalokowaną

A jak sprawdzisz jak to robi malloc heap alokator.
To zobaczysz, że akurat ta wersja domyślna na gcc opakowuje każde zaalkowane bajty w strukturę, która zawiera ile bajtów jest w danym bloku.

Alokator jest częścią bibliotek systemowych i nie ma nic wspólnego z gcc. Na linuksach/uniksach jest częścią libc.
Można go łatwo podmienić po skompilowaniu programu na inny.
Wyciągasz ogólne wnioski na podstawie jednej konkretnej implementacji.
Alokator nie musi marnować pamięci na długość zablokowanego bloku, dobre alokatory robią to inaczej.

Jedna tablica to jest jeden cacheline i wyobraź sobie, że int leży 2 bajty w jednej tablicy i 2 bajty w drugiej, to musisz odwołać się do dwóch oddzielnych cachelinów i potem splitnąć do jednego rejestru, a normalnie jak jest wyrównane to zawsze rejestr się odwołuje do jednego cacheline.

Program nie wie nic o liniach cache, to dopiero CPU to robi.
Wyrównanie stosuje się z zupełnie innego powodu - danych które nie są wyrównane nie można adresować. Tzn. jak zrobisz wskaźnik do inta, który nie jest wyrównany, to dereferencja takiego wskaźnika to UB. Przy czym procesory zwykle udostępniają osobne instrukcje do pracy z danymi niewyrównanymi, więc to nie jest taka bezwzględna przeszkoda, ale komplikuje. No i dostęp do niewyrównanych danych jest często kosztowniejszy. NIemniej zasady wyrównania wymagają aby 4-bajtowy int był wyrównany do wielokrotności 4 bajtów, 8-bajtowy wyrównany do 8 bajtów, a 16-bajtowy wyrównany do 16 bajtów, a nie zawsze 8 bajtów jak napisałeś wyżej.

Przykładowo jeśli zaalokuje inta 4 bajty to padding wyrówna mi go do 8 bajtów, bo to najmniejsze słowo na jakim działa cache.

Linia cache na intelu ma 64 bajty.
A z wyrównaniem do 8 bajtów to bajdurzysz:

   let x: u32 = 0;
   let y: u32 = 0;
   
   println!("{:p}", &x);
   println!("{:p}", &y);

Wynik:

0x16d01b190
0x16d01b194

Różnica adresów jest 4 bajty. Kompilator nie wstawił żadnego paddingu bo wyrównujemy zawsze do rozmiaru inta.
Wiec gdzie jakiś cache Ci nie działa? Coś poplątałeś z tym wyrównaniem ;)

Jeśli miałeś na myśli wyrównanie stosowane domyślnie przez alokator sterty, to ponieważ alokator nie wie do czego będę używał przydzielonej pamięci, więc na wszelki wypadek musi wyrównać tak, abym pod zwrócony wskaźnik mógł zapisać dowolny typ obsługiwany natywnie przez procek. Dlatego np. u mnie wyrównuje do 16B. Natomiast kompilator wie z jakimi rozmiarami ma do czynienia, bo zna typ, więc na stosie może alokować bardziej granularne, nawet co 1, 2, 4 bajty w zależności od rozmiaru struktury.

// dopisane:

Po podmianie alokatora na jemalloc, lista adresów z kolejnych alokacji 4-bajtowego inta:

0x104c08008
0x104c08010
0x104c08018
0x104c08020
0x104c08028
0x104c08030
0x104c08038
0x104c08040
0x104c08048
0x104c08050
0x104c08058
0x104c08060
0x104c08068
0x104c08070
0x104c08078
0x104c08080

Idzie co 8 bajtów.
I teraz uważaj, jak alokuje 64-bitowe inty (typu u64), to też adresy wzrastają co 8 bajtów.
Więc jakie nagłówki?!

(a 8 bajtów dlatego, że specyfikacja jemalloc określa najmniejszy bucket na 8 bajtów)

Wydaje mi się, że jak alokujesz mallociem to zawsze masz zapewniony aligment. Czyli mpżesz zalokować 1 bajt a i tak zmarnujesz 4 albo 8 bajt etc. Bo kolejnej pamięci nie dostaniesz na wcześniejszej pozycji. Malloc nie wie czy wsadzasz tam char czy int czy cokolwiek. Królik dajesz przykład ze stacka gdzie kompilator wie, że to są inty więc może je ścisnąć. Takie moje na zdrowy chłopski rozum hehe ( edit napisałem w bitach wcześniej przez co ucierpiała czytelność )

WeiXiao napisał(a):

wtf? a czym jest LinkedListNode?

Klasą.

YetAnohterone napisał(a):

nie trzeba układać elementów całej kolekcji, wystarczy przy każdym elemencie trzymać indeks następnego. Wyjdzie O(1). Co prawda elementy takiej listy będą porozrzucane po kolekcij, ale to o niebo lepiej, niż porozrzucanie elementów listy po całej pamięci. Głupia implementacja takiej 'linked listy' poniżej.

No linked lista w oparciu o zwykłą listę, no tak faktycznie niezbyt sprytne i niczego nie pokazuje.

Gdyby chcieć mieć tablicę pod spodem, to też byś dodawał na jej koniec, czy trzymał gdzieś oddzielną tablicę pustych (usuniętych) indeksów do reużycia?

będzie zamortyzowane O(1).

Ale jakim cudem?

@somekind , naprawdę nie rozumiem, w czym problem?

Dowód, że dodawanie do listy ma zamortyzowaną złożoność stałą.

Załóżmy, że jeśli lista ma n elementów, to dodanie do niej kolejnego to jest 1 operacja, jeśłi lista nie jest pełna, i n+1 operacji (kopiowanie + dodanie), jeśli lista jest pełna.

Lista rośnie następująco: jej rozmiar jest zawsze potęgą dwójki. Gdy dodajemy 2^k-ty element, wtedy capacity rośnie dwukrotnie (i wykonujemy 2^k+1 operacji); wpp jej capacity się nie zmienia i dodawanie nowego elementu to 1 operacja.

Dodajemy do listy n elemnetów. Twierdzę, że nie wykonamy więcej, niż 4n operacji.

Indukcja.
Baza. Gdy lista jest pusta, to wykonujemy 1 operację. 1 < 2, się zgadza.
Krok. Lista ma 2^k+m elementów, m < 2^k. Dodajemy element 2^k+m+1-szy. Z zał. ind. dodanie 2^k eltów to mniej niż 4*2^k operacji. Zatem dodanie 2^k+m eltów to mniej niż 4*2^k+m operacji. Interesującym przypadkiem jest tylko ten, gdy m+1 = 2^k. Wykonaliśmy mniej niż 4*2^k+m < 4*2^k+2^k=5*2^k operacji. Kopiujemy całość i dodajemy kolejny element, to jest kolejne 2*2^k operacji. Razem 7*2^k operacji. Tymczasem eltów jest 2*2^k. Ograniczenie jest, że nie możemy wykonać więcej, niże 4*2*2^k = 8*2^k. Zgadza się: 7*2^k < 7*2^k.

Owszem, dodawanie kolejnego elementu ma pesymistyczną złożoność O(n), ale zamortyzowaną O(1). Bo jeśli wykonujemy n dodawań, z których wszystkie naraz szacują się przez 4*n, no to wychodzą średnio 4 operacje na dodawanie.

Tyle jeszcze ze studiów pamiętam.

somekind napisał(a):

wtf? a czym jest LinkedListNode?

W tym kontekście LinkedListNode jest referencją na obiekty klasy LinkedListNode. Referencje w językach takich jak Java/C# to wskaźniki, które są mocno okrojone z ficzerów w taki sposób, żeby były jak najmniej szkodliwe w tym co robią. Prawdziwe referencje znane np. z C++ to strasznie problematyczny ficzer w języku, który mocno komplikuje język dająć mało w zamian

Jeśli coś jest na tablicach, to z definicji nie może być "linked listą", tylko najwyżej "listą".

To co o Ruście jest napisane trzeba interpretować inaczej.
Wyobraź sobie, że masz linked listę, ale zamiast malloc wołasz mój_customowy_alloc. A ten customowy alloc, będzie działać podobnie jak normalny malloc, tylko będzie się starał trzymać dane obok siebie w miarę możliwości.
No i to co w Ruście musisz zrobić, to ten alokator ręcznie symulować - tzn trzymać indeks w tablicy, i ręcznie dereferencjonować, zamiast od razu mieć sumę &początek_tablicy+indeks.

Bo najpopularniejsze podręczniki z algorytmiki i struktur danych powstały w czasach gdy pamięć byłą zwykle niewielka i droga a CPU to było coś co zajmowało czasem kilka płyt drukowanych i cache był nawet w poważnych maszynach jedynie opcją którą można było sobie kupić (za gruby hajs na dodatkowej płycie drukowanej) albo dana architektura nawet nie posiadała żadnego cache i nie dorobiła się na szerszą skalę implementacji od firm trzecich więc cache nie było standardem. Więc ilość danych na których się pracowało, pamięć wirtualna i przełączanie kontekstu między procesami kiedyś [o ile w ogóle występowały bo wszystko mogło sobie lecieć wsadowo] to nie to co teraz. Inne były koszty implementacji i inne były wybory programistów. Przy kilkudziesięciu kilobajtach RAM trochę innaczej się wybiera implementacje niż przy kilku megabajtach.

Wielu programistów obecnie też nie zapuszcza się w aż takie niuanse nawet na studiach informatycznych. Kiedyś trafiało się to częściej bo IT i informatyka oraz same CPU były znacznie mniejszymi działkami i był czas oraz fizyczna możliwość upchnąć to w progrmie. A były też jeszcze przypadki kiedy trzeba było rozumieć jak CPU działa żeby w ogóle móc z komputera korzystać w najbardziej pionierskich czasach.

Taka lista to zwykły graf kierunkowy, czasem się robi gorsze rzeczy, ale rozwiązując znacznie trudniejsze problemy inaczej ich nie zamodelujesz, graf jest najbardziej abstrakcyjną i wszędzie we wszechświecie wsystępującą strkturą danyhc, a w dodatku to już jest martwy temat czemu w nekromancję się bawisz?

Co do cache, to jego implementacja jest piękna, normalnie kości pamięci mają dostęp dosyć wolny więc równocześnie na raz pozwala na duży speed.

Pomijając tłumaczenie TLB, to ma się zwykle dwa rodzaj cache zwykłe i set associative, te pierwsze nie są używane, a działanie jest proste każdy adres, adres sam w sobie jest indexem w tablicy cache, a jak jest set associative to wiele podobnych adresów mogą być na raz załadowane bo cyklicznie się powtarzają, każdy taki adres to cache line L1, a L2 to dwa takie cache liny pierwszy i drugi z rozbiegu jest wczytywany, per cpu, ogólnie wyszukiwanie adresu w którym cache jest jest dosyć ciekawe mamy algorytmy typu hash map i jest bardzo efektywny, perfekt hash map jeśli każdy typ danych po zahashowaniu daje idealnie jeden index w tablicy to jest to perfekt, ale życie bywa brutalne i ciężko tak dobrać dane i algorytm, bo dane mogą się zmieniać, żeby zawsze był najszybszy dostęp.

Tworząc procesory w typowym fpga, można pokusić się o układ zwany content adresable memory, gdzie jednocześnie wyszukujemy wartość we wszystkich komórkach i robimy coś takiego jak if, ale na wszystkich np. tysiącach komórek jednocześnie, działa to jeszcze szybciej niż hash mapa, która nie ma kolizji i jest perfekt bo nie trzeba hasha nawet liczyć.
Wszystko się wykonuje równolegle.

Ciekawe są ataki na cache, side channel strasznie je lubię, per cpu mamy l1, l2 cache i l3 jest współdzielone.
Wiedząć, że mamy np. 8 set associative cache, to jeśli jakiś proces działa na danym cache i wiemy który to cpu, to też można zmusić system, żeby na tym cpu odpalał ci aplikację.
Ataki typu meldown i spectra są dosyć ciekawe jak wykorzystują takie podatności, procesor żeby być szybszym wczytuje czasem do przodu parę linijek i je wykonuje, dodatkowo procesor jeśli operacje nie są zależne może je wykonać równolegle.

Czasem źle jakiś branch policzy, który nigdy się nie wykona i odwołuje się do null pointera, procesor go otworzy, ale exceptiona nie dostaniesz za segmentation fault.
Jeśli masz listę adresów o wielkości cache line, możesz je wszystkie wyzerować, żeby w cache nie były dostępne, każdy musi być zassany, a w swoim kodzie dać adres kernela do odczytu, tak branch prediction oszukując, żeby przypadkiem odczytał kernela, potem wartością odczytaną posłużył się do odczytania cache line w twojej tablicy, potem się iteruje po tablicy i sprawdza czas dostępu, ten który ma któtki czas czyli ten index oznacza wartość w kernel space.

Ten atak był jednym z lepszych, teraz podobne w apple procesorze wyszły.
Teraz ludzie myślą żeby robić zabezpieczenia na poziomie cache gdyż to jest dosyć wrażliwe miejsce i powstaje tam masa ataków, wybierasz adresy takie, żeby cache całe zinwalidować.
Jeden proces może drugiemu procesowi invalidować cache liny bo są set associative i cpu współdzieli cache na tym samym rdzeniu.

Nie wiem co tu kombinujesz - odkrywasz Amerykę?

Listy są często szybsze od tablic, bo to polega na sortowaniu wraz z danymi, czyli nie chodzi o to że jakieś int sortujemy,
lecz całe struktury danych, np.:
nazwisko + imię + adres + pesel, tel... 100 czy czy 1000 bajtów - tego nie wiemy, zatem statyczna tablica już jest spalona!

i dodatkowo: my nie wiemy ile takich elementów jest: 100 czy milion.

Twoja tablicowa metoda przegra w 99% przypadków: czasowo i pamięciowo, bo... jest zbyt naiwna.

kejsz mówisz? tego w ogóle się nie liczy - bo nie ma znaczenia w przypadku dużych danych.

Co najwyżej możesz stworzyć hybrydę: B-drzewa zamiast binarnych, bo tu masz te swoje strony - tablice... i to faktycznie często wyjdzie lepsze.

Elementy tablicy jak najbardziej da sie również posortować.

Można w postaci tablicy przechowywać też grafy.

Można w postaci tablicy przechowywać nieposortowane elementy i w postaci tablic przechowywać różne porządki elementów tej nieposortowanej tablicy.

Można też te same powielone dane przechowywać w tablicach o różnych porządkach elementów. Jeśli mamy kupę taniej pamięci, elementy prawie się nie zmieniają i prawie nigdy nie trzeba sortować na nowo danych oraz raczej przez dłuższy czas czytamy dane wedle jednego porządku to może to być bardzo racjonalne i szybkie podejście.

Debaty o tym czy lepiej użyć tablic czy list są ciężkie, bo można różnie podejść do całej masy założeń typu ile pamięci i jak przydzielamy sobie na początek, jakie operacje i jak często będą wykonywane, czy da się coś powiedzieć o fragmentacji danych w pamięci fizycznej (ta może wystąpić również w przypadku tablic jeśli przykładowo pamięcią zarządza system operacyjny ze swym podsystemem pamięci wirtualnej [a ten może (ale nie musi) być zaimplementowany w oparciu o listy] a nie dzialamy na surowych adresach jak ma to miejsce w programowaniu rzeczy bardziej "bare metal") oraz kwestie przenośności kodu między różnymi platformami.

Można oczywiście też tworzyć hybrydy jak listy tablic.

Jeżeli ktoś bardzo zechce to może też stworzyć hardware gdzie nawet listy dwukierunkowe czy wielokierunkowe będą wspierane szybko na niskim poziomie np dzięki wyspecjalizowanej pamięci umożliwiającej odczyt i/lub zapis dużo większej ilości danych w jednym takcie zegara niż "normlne" (nie posiadające takich mechanizmów) CPU. Jak ma się hajs i się to opłaca można i tak szaleć.