Inteligentne przydzielanie pamięci.

Tak się zastanawiałem czemu nie powstał taki język gdzie przydzielanie pamięci danej zmiennej/obiektowi robi się bardziej "inteligetniej". Zapewne mam za małą wiedzę dotyczącą jak działa komputer (a raczej przydzielanie pamięci dla niego)

Chodzi o to że np. int zajmuję 4 bajty. A często jest on używany do małych liczb. Takie liczby które spokojnie się zmieszczą na np 6 bitach. Czasami mamy jakieś stałe liczby które są małe. A jakby definicje z jednej prostej zamienić na taką

Stable int variable = 5;

Stable[4] int variable;

nStable int variable;

kompilator widząc stable oblicza ile potrzebne będzie bitów (w tym przypadku 3) i tylko tyle rezerwuje dla tej zmiennej pamięci.
widząc Stable[4] rezerwuje 4 bity
natomiast jak widzi nStable to przydziela standartowo 4 bajty

myślałem także że gdy nStable to może dynamicznie powiększać rozmiar miejsca zarezerwowanego (zaczynawszy od 1 bajta). Gdy sprawdzi że się liczba nie zmieści to wtedy zwiększa mu przydzieloną pamięć. Gorzej byłoby z tym gdyby wpisywanie odbywało się dynamicznie. Ale sądzę, że jest też na to jakiś sposób.

Nie wiem czy programy działały by szybciej, na pewno zajmowały by mniej miejsca w pamięci. Na logikę działały by szybciej, ale zapewne jest jakiś optymalizator który skacze po bajtach a nie po bitach (zbiera dane jak sieć rybacka).

Mógłby mi ktoś rozjaśnić sytuację tego?

Co do wydajnosci:
http://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf
3.6, a w szczegolnosci 3.6.4.

• Specyfikacje jezykow nie pozwalaja na to o czym piszesz, ze wzgledu na gwarantowany zakres wartosci typow. Kompilator nie ma prawa wiedziec, czy nie upakujesz tam wiecej danych w trakcie dzialania programu. Stale i tak sa zamieniane na ich reprezentacje w czasie kompilacji.

myślałem także że gdy nStable to może dynamicznie powiększać rozmiar miejsca zarezerwowanego (zaczynawszy od 1 bajta). Gdy sprawdzi że się liczba nie zmieści to wtedy zwiększa mu przydzieloną pamięć.

To by byla katastrofa.
Przemysl taki scenariusz:

1. Mam zmienna typu int inicjalizowana liczba 3 (Wg Twoich rozwazan 2 bity starczaja), zmienna ta jest pod adresem 0x4000.
2. Tworze druga zmienna typu `int incjalizowana liczba 15 (4 bity). Teraz jest zagadka, gdzie ona bedzie ulokowana w pamieci.
   • Czy Od razu po zmiennej numer 1?
   • Czy na nastepnym bajcie?
   • Czy rozmiar zmiennej dalej, czyli adres 0x4004?

W 2 pierwszych przypadkach, zeby powiekszyc ta liczbe do wartosci np. 256 kompilator musial by trzymac zmienna pofragmentowana i skladac ja przy kazdym odwolaniu do pamieci tymczasowej, a potem zapisywac te fragmenty.
W 3 przypadku nie oszczedzamy pamieci wcale, bo i tak nic tam sie nie da wlozyc.

Zmniejszanie liczby bitów poniżej 8 nie ma najmniejszego sensu, bo odczytujesz i tak cały bajt, więc potem go kroisz i znowu przekazujesz cały bajt.

Bajt jest jak atom, niby jest coś mniejszego ale nic z tego nie zrobisz (o ile nie chcesz wynaleźć antygrawitacji, i badać ciemną materię :) )

Chodzi o to że np. int zajmuję 4 bajty. A często jest on używany do małych liczb. Takie liczby które spokojnie się zmieszczą na np 6 bitach. Czasami mamy jakieś stałe liczby które są małe.

Próbujesz być inteligentniejszy od kompilatora... a przy tym w Twoim rozumowaniu są trzy nielogiczności:
1.Najmniejsze rejestry (przynajmniej w architekturze x86, nie wiem jak w reszcie) mają tak czy siak jeden bajt (ah, al...), a procesor tak czy inaczej w pamięci operuje na bajtach, a nie bitach (czyli nie jest w stanie wczytać z pamięci np.dwóch bitów, tylko od razu cały bajt).
2.Programista powinien (był) zadbać o dobry dobór typów zmiennych - w tym wypadku jedno-bajtowy int8/uint8.
3.Oszczędzanie bitów danych to paranoja!*

Nie wiem czy programy działały by szybciej, na pewno zajmowały by mniej miejsca w pamięci.

No tak, zaoszczędzenie paru bajtów to jak wygranie z rakiem...

---

`*` jeżeli mowa o aplikacjach typowo desktopowych lub na telefony, ponieważ ofc.w przypadku pisania softu dla jakiegoś procesora, gdzie do dyspozycji jest zaledwie kilkaset bajtów, to walka o każdy bit jest ważna :P Natomiast z głównego postu wynika, że chodzi o aplikacje bardziej na PC-ty itp.

Pakowanie liczb w mniejsze jednostki pamięci może mieć sens lub nie - w zależności od okoliczności.
Dlatego powstały UTF-8, pola bitowe (indeksy wektorowe, bitmapy 1bpp, set w Pascal) i bitplany (bitmapy).

Ogólnie z tego co wiem to zaleca się minimalizowanie zajętości pamięci - ze względu na cache. Małe struktury lepiej w nim się mieszczą, przez co dostęp do nich jest wielokrotnie szybszy, mimo że trzeba poświęcić więcej cykli na rozpakowanie danych.

Edit: małe uzupełnienie:
http://www.roguewave.com/DesktopModules/Bring2mind/DMX/Download.aspx?entryid=1134&command=core_download&PortalId=0&TabId=607

Ale autor mówi o optymalizacji (jak rozumiem prędkość), a to nie ma sensu.

Sam kiedyś ubijałem 8 booleanów do 1 bajta, ale to było na odtwarzacz mp3 gdzie zaciekle trzeba było walczyć o każdy bajt kodu oraz pamięci. Ale dziś, nawet byle jakie scalaki już mają większe zasoby, gdzie ten bój nie ma już sensu.

Zrobiliśmy się marnotrawni jeśli chodzi o zasoby, ale co z tego, skoro jesteśmy w nie "bogaci"?

fasadin napisał(a):

myślałem także że gdy nStable to może dynamicznie powiększać rozmiar miejsca zarezerwowanego (zaczynawszy od 1 bajta). Gdy sprawdzi że się liczba nie zmieści to wtedy zwiększa mu przydzieloną pamięć. Gorzej byłoby z tym gdyby wpisywanie odbywało się dynamicznie. Ale sądzę, że jest też na to jakiś sposób.

Możesz założyć że to tylko format przechowywania danych (w pliku, buforze) i wzorować się np. na kodowaniu UTF-8.
Zmiana wielkości pojedynczej zmiennej będzie mało sensowna bo doprowadzi do dużej ilości małych obiekcików / bloków danych, co będzie trudne do optymalizacji. Dlatego lepiej, gdyby zmienna skalarna miała maksymalny rozmiar.

A być może w ogóle szukasz nie tam gdzie trzeba - w końcu masz szablony (w C++) lub typy generyczne (Java, C#) - jeśli chcesz robić algorytmy / struktury operujące na możliwie najmniejszej (w danym kontekście) jednostce pamięci.

Z punktu widzenia procesora 64bit (przykład) nie ma znaczenia, czy podasz mu 1 bit czy 64, bo daną operację (arytmetyczną lub logiczną) i tak wykona w ścisłej ilości taktów zaokrąglając twoje bity do pełnej wielkości rejestru, czyli 64 bit. Przy zapisie i pobieraniu z pamięci limitując się do bitów wprowadzasz opóźnienia spowodowane tym, że najmniejsza jednostka RAM to bajt. Biorąc też pod uwagę, że procesor raczej po bajcie z RAMu nie odczytuje, a w blokach wielkości cache procesora (lub całkowitej części), to żonglerka bajtami a tym bardziej bitami się nie opłaca.

Podobna sprawa wygląda z dyskami twardymi. Tam też nie odczytuje się po bajcie, bo i tak w najlepszym razie dostaniesz ilość danych wielkości sektora. Sektor ostatnio zajmował 512 bajtów (nie wiem jak jest w nowych dyskach), więc odczytując ilości mniejsze i tak nie zyskasz na prędkości, a raczej spowolnisz aplikację. I znów w nowszych dyskach cache dysku nie odczyta ci tylko jednego sektora, a jakąś większą określoną ilość, by w razie odczytu sekwencyjnego mieć już gotowe dane w cache i nie musieć z powrotem mielić głowicą. W dyskach SSD może być trochę inaczej.

"Tak się zastanawiałem czemu nie powstał taki język gdzie przydzielanie pamięci danej zmiennej/obiektowi robi się bardziej "inteligetniej". Zapewne mam za małą wiedzę dotyczącą jak działa komputer (a raczej przydzielanie pamięci dla niego)"

Ależ są takie języki, a raczej kompilatory do nich, gdzie przy każdym uruchomieniu programu kompilator bierze pod uwagę maszynę na jakiej został uruchomiony. Tak działa wirtualna maszyna Javy, która potrafi tak dobrać parametry kompilacji, że program w Javie może być (i często jest) szybszy od odpowiednika w C++ kompilowanego na wiele maszyn. To "mulenie" na początku uruchamiania Javy to właśnie wstępna kompilacja. Co ciekawe, Java prowadzi statystyki w czasie działania programu (próbuje różne wersje kodu) i może dzięki temu jeszcze bardziej przyspieszyć. Dlatego w nietrywialnych i długo działających programach, gdzie wydajności nie może w trywialny sposób zoptymalizować jedna osoba (nie ogarnia ilości kodu), Java jest szybsza od C++.

Rozumiem, że piszesz jako anonim bo nie jesteś pewien niczego co napisałeś? To w sumie dobrze dla Ciebie... 1) Ma znaczenie ile danych przeczytasz - choćbyś je czytał z cache level 1, 2) odczyt sektor po sektorze skończył się jakoś w okolicach DOS-a chyba 3) teza że nie warto czytać jednostek mniejszych niż 512 B cudownie łączy w sobie samozachwyt z niewiedzą. 4) Ufność, że Java prowadzi w statystykach to już po prostu materiał na flame war, nic więcej

Tworzenie konta tym bardziej nie chroni przed pisamiem bzdur i nie dodaje do IQ.

1. Ma znaczenie, ale procesor i tak wczyta blok, a nie pojedynczy bajt czy bit. Jeżeli sobie ułożyłeś dane w tablicy, to dobrze. Gorzej jak odczytujesz z bloków, które są bardziej odległe (większe niż cache).
2. Odczyt po sektorach jest robiony w sterowniku, to podstawowa jednostka danych w HDD. Pisząc 1 bajt zapisujesz cały sektor. Oczywiście takim jak ty wydaje się inaczej, ale to wina szkoły.
3. Używanie jednostek mniejszych od sektora powoduje wielokrotne odczyty lub zapisy do tego samego sektora - czyli opóźnienia.
4. Java prowadzi statystyki dot. wykonywania się różnych części programu, w statystykach też prowadzi jak sam zauważyłeś. Nawet czytać nie potrafisz.
5. Poziom tego wątku jest niski,a odpowiedzi mylące. Zamiast w prost odpowiedzieć człowiekowi jak to wszystko działa pod spodem piszecie farmazony. Żaden z was nie ma pojęcia o niskopoziomowych sprawach. Tak więc wolę pisać jako anonim. Nie będę sobie psuć reputacji. Oczywiście człowiek ma rację z matematycznego punktu widzenia i dobre intencje, ale znajomość matematyki nic tu nie pomoże.

Biorąc też pod uwagę, że procesor raczej po bajcie z RAMu nie odczytuje, a w blokach wielkości cache procesora (lub całkowitej części), to żonglerka bajtami a tym bardziej bitami się nie opłaca.

Zależy - jeżeli uda się zmieścić więcej danych w mniejszej ilości pamięci to cache może zostać lepiej wykorzystany i wydajność wzorśnie. A kilka operacji logicznych do wyciągnięcia poszczególnych bitów zajmuje stosunkowo mało w porównaniu z dodatkowymi dostępami do RAMu.

2. Odczyt po sektorach jest robiony w sterowniku, to podstawowa jednostka danych w HDD. Pisząc 1 bajt zapisujesz cały sektor. Oczywiście takim jak ty wydaje się inaczej, ale to wina szkoły.
3. Używanie jednostek mniejszych od sektora powoduje wielokrotne odczyty lub zapisy do tego samego sektora - czyli opóźnienia.

System operacyjny i tak cache'uje odczyty/zapisy z/do dysku więc nie ma większego znaczenia czy sobie czytasz plik po jednym bajcie czy po 512 bajtów. Szybkość będzie podobna (chyba że specjalnie sobie wyłączysz wszystkie cache poczynając od tego wbudowanego w firmware dysku na systemowym i aplikacyjnym cache'u kończąc).
Ważne jest, żeby nie skakać po całym pliku nie powodować cache missów.

Zależy - jeżeli uda się zmieścić więcej danych w mniejszej ilości pamięci to cache może zostać lepiej wykorzystany i wydajność wzorśnie. A kilka operacji logicznych do wyciągnięcia poszczególnych bitów zajmuje stosunkowo mało w porównaniu z dodatkowymi dostępami do RAMu.

Tak, ale nie zawsze. Wątpię czy w ogóle. Najmniejszą jednostką danych jest bajt i na takiej małej jednostce możesz prowadzić obliczenia bez dodatkowych cykli zegara. Każda ułamkowa część wymaga obliczenia offsetu i złożenia danych. Jeżeli sumuję elementy takiego strumienia, załóżmy 100 bajtów, to odczyt i suma dadzą 200 cykli zegara (przykładowo, pomijam obliczenia pomocnicze, typu np. zwiększanie licznika). Jeżeli masz coś upakowane w bitach, to dochodzi obliczenie przemieszczenia, czyli, odczyt wartości, znalezienie offsetu, wyłuskanie wartości, uzupełnienie zmiennej pomocniczej (przesunięcie i aktualizacja) i dopiero suma, 6 operacji, czyli 600 cykli zegara. Dodatkowo kolejnych przemieszczeń danych nie mamy podanych jak na tacy i za każdym razem trzeba liczyć offset. Załóżmy, że co 3 bajt trzeba obliczyć na piechotę, więc z 200 w najlepszym razie robi się 260 cykli, które im więcej danych tym coraz bardziej rosną (złożoność liniowa), aż do momentu gdy suma dodatkowych cykli nie przekroczy kosztu odczytu danych, które ktoś zapodałby po ludzku, czyli jak w każdej normalnej książce pisze.

System operacyjny i tak cache'uje odczyty/zapisy z/do dysku więc nie ma większego znaczenia czy sobie czytasz plik po jednym bajcie czy po 512 bajtów. Szybkość będzie podobna (chyba że specjalnie sobie wyłączysz wszystkie cache poczynając od tego wbudowanego w firmware dysku na systemowym i aplikacyjnym cache'u kończąc).
Ważne jest, żeby nie skakać po całym pliku nie powodować cache missów.

Oczywiście, ale to tylko w trywialnych przypadkach, gdy takie cache jest. Niemniej i tak zapodając bufor o wielkości różnej od wielokrotności sektora twój program może dostawać w benchmarku bęcki od takiego, który to uwzględni. Co oczywiście będzie widać na porównaniach, a klient weźmie produkt konkurencji, bo był szybszy o 0,1%. Life is brutal. Dlatego lepiej skupić się na lepszym produkcie niż tracić czas na optymalizację tego 0,1%.

RS, coś tam wiesz, ale masz wiedzę z czasów 386.
W dzisiejszych czasach liczba cykli z manuala nie ma znaczenia - poza rzadkimi algorytmami, liczącymi coś w miejscu. Większość algorytmów jeździ po pamięci.
Liczy się wykorzystanie cache procesora. Algorytm liczący coś, z losowym dostępem, na tablicy bajtów, która akurat mieści się w cache L2 będzie nawet 10 razy szybszy od tego samego algorytmu, ale na tablicy dwordów nie mieszczącej się w cache.

Dlatego vector<bool> to tablica bitów (zajmująca oczywiście całkowite bajty) - zmniejszenie użycia pamięci jak najbardziej się opłaca.

Dlatego @fasadin ma rację - zmniejszanie wielkości ma sens.

Po jak największym zmniejszeniu zużycia pamięci, ważniejsza od sumarycznej liczby cykli (wg manuala) jest niezależność instrukcji. Nie można traktować dzisiejszych procesorów jak szybszej wersji 386.

Wiesz dlaczego x86/amd64 tak drastycznie wygrywa wydajnością z armami? Bo instrukcje mają różne długości i generalnie, te częściej używane są krótsze, dzięki czemu o wiele więcej mieści się w cache. Kiedyś była to wada, bo dekoder zwalniał kod w porównaniu do cpu ze stałymi instrukcjami, ale dziś jest to ogromna zaleta.

Ja się trochę pogubiłem czytając poszczególne posty. Tak jakby były trzy fronty. Fajnie by było, że jak dana osoba piszę jak ona to widzi to odnośnie jakiej architektury poparte jakimiś źródłami.

Tak, ale nie zawsze. Wątpię czy w ogóle. Najmniejszą jednostką danych jest bajt i na takiej małej jednostce możesz prowadzić obliczenia bez dodatkowych cykli zegara. Każda ułamkowa część wymaga obliczenia offsetu i złożenia danych. Jeżeli sumuję elementy takiego strumienia, załóżmy 100 bajtów, to odczyt i suma dadzą 200 cykli zegara...

Przy obecnej komplikacji procesorów takie obliczenia nie mają sensu. Najlepiej zrobić benchmark (jak komuś się chce :P).

Oczywiście, ale to tylko w trywialnych przypadkach, gdy takie cache jest.

Cache jest zawsze i trzeba się nieźle postarać, żeby powyłączać wszystkie cache. W zasadzie robi się to tylko przy bazach danych, które potrzebują transakcyjności.

Niemniej i tak zapodając bufor o wielkości różnej od wielokrotności sektora twój program może dostawać w benchmarku bęcki od takiego, który to uwzględni. Co oczywiście będzie widać na porównaniach, a klient weźmie produkt konkurencji, bo był szybszy o 0,1%. Life is brutal. Dlatego lepiej skupić się na lepszym produkcie niż tracić czas na optymalizację tego 0,1%.

Z pliku czyta się dane tyle ile potrzebujesz. Jak zaczniesz kombinować w stylu "czytam tylko po sektorze" to możesz sobie tylko zaszkodzić. Jeżeli dane które odczytujesz nie będą wyalignowane na dysku (a jaką masz gwarancje, że będą jeżeli czytasz zwykły plik?) to czytając 512 bajtów tak na prawde możesz sobie wczytać dwa sektory zamiast jednego.

Co oczywiście będzie widać na porównaniach, a klient weźmie produkt konkurencji, bo był szybszy o 0,1%. Life is brutal. Dlatego lepiej skupić się na lepszym produkcie niż tracić czas na optymalizację tego 0,1%

W której branży 0.1% robi różnice klientowi?
Jeżeli na prawdę zależy Ci na wydajności odczytów dyskowych to użyjesz memory mapped file zamiast technik z czasów DOSa :p

fasadin napisał(a):

Ja się trochę pogubiłem czytając poszczególne posty. Tak jakby były trzy fronty. Fajnie by było, że jak dana osoba piszę jak ona to widzi to odnośnie jakiej architektury poparte jakimiś źródłami.

No to zobaczmy jakie możesz miec zyski z pakowania danych po bitach.
http://4programmers.net/Pastebin/2363
Problem: policzyc jedynki w ciągu.
Dla PACKED=true jedynka jest reprezentowana jako pojedynczy bit
Dla PACKED=false jedynka jest reprezentowna jako pojedynczy bajt
Czasy z wykonania: VS2012 Release x64
PACKED= true 11ms
PACKED= false 204ms
Czyli czasem można zyskać na spakowaniu wszystkiego w bity. Natomiast jak widzisz rezultat nie jest powalający - ~200ms nie robi wielkeij różnicy dla tablicy o takim rozmiarze.
Do tego na innym kompilatorze możliwe, że dostaniesz inny wynik. Przy innym problemie pakowanie wszystkiego po bitach może wręcz pogorszyć wydajność (np. zwiększa ilość generowanego kodu, który nie mieści się w cache'u).
Więc odpowiadając na pytanie "dlaczego nie powstał taki język" - odpowiedź brzmi - taka optymalizacja jest słaba i nie zawsze przyniesie dobry rezultat. Sam musisz zdecydować kiedy tego potrzebujesz a (niektóre) języki ci to umożliwiają.

0x200x20 napisał(a):

Tak, ale nie zawsze. Wątpię czy w ogóle. Najmniejszą jednostką danych jest bajt i na takiej małej jednostce możesz prowadzić obliczenia bez dodatkowych cykli zegara. Każda ułamkowa część wymaga obliczenia offsetu i złożenia danych. Jeżeli sumuję elementy takiego strumienia, załóżmy 100 bajtów, to odczyt i suma dadzą 200 cykli zegara...

Przy obecnej komplikacji procesorów takie obliczenia nie mają sensu. Najlepiej zrobić benchmark (jak komuś się chce :P).

Mają sens, tylko trzeba wiedzieć jak to robić. A jest to na tyle skomplikowane, że lepiej jak napisałeś zrobić benchmark.
Obecnie procesory (jakoś tak od Pentium I) mają pipeline'y, cache instrukcji, cache danych, więc sumaryczna liczba cykli dla wszystkich instrukcji <> czas wykonania.

0x200x20 napisał(a):

Czyli czasem można zyskać na spakowaniu wszystkiego w bity. Natomiast jak widzisz rezultat nie jest powalający - ~200ms nie robi wielkeij różnicy dla tablicy o takim rozmiarze.

Test jest powalający, w ogóle że też Ci się chciało... Wynik 20/1 pokazuje wprost że warto oszczędzać pamięć.
To jest test syntetyczny, co oznacza, że w realnym zastosowaniu takich wywołań / funkcji jest wiele. Po zsumowaniu może się okazać że 190 ms rośnie do wielkości nawet minut.

No właśnie dlatego dobre porównanie moim zdaniem to albo oba z rozszerzeniami albo oba bez (to pierwsze lepsze). Bo że dedykowana instrukcja będzie szybsza to niewielka niespodzianka. A co z zastosowaniami, dla których nie ma takiej instrukcji i trzeba na bitach operować ręcznie? - Endrju 10 minut temu

http://4programmers.net/Pastebin/2364
Tym razem ze softwareowym popcountem (kod wziety z wikipedii).
Zamiast 11ms dostaje 22ms. Więc znaczniej różnicy nie ma między sprzętowym a softwareowym popcountem nie ma.
Za to cały czas jest różnica między spakowaną a nie spakowaną reprezentacją :P

od takich rzeczy są pola bitowe żeby gęsto upakować dane. Ale sądze że jak by można było np tworzyć tylu bitowe zmienne ile chcemy np jak by się dało stworzyć zmienna jedno bitową to by były kłopoty z adresowaniem zmiennych gdyż bitów nie da się adresować i tak czy siak trzeba by było i tak to jakoś wypełnić. np kompilator wypełnia zerami ramkę stosu zerami żeby adresy miały równe liczby.