On Friday, December 4, 2015 at 8:11:03 PM UTC+1, Adam M wrote:
> On Friday, December 4, 2015 at 10:17:02 AM UTC-5, Borneq wrote:
> > W dniu 2015-12-04 o 15:51, Adam M pisze:
> > > Dlaczego struktura bitowa raczej unia struktory bitowej z odpowiadajacym
unsigned int lub unsigned long - to jest standardowe rozwiazanie np przy
programowaniu MCUs
> > > Aby znalezc wolny bit niezaleznie od zajetosci potrzeba cztery podzialy 32, 16,
8, 4 i 4 rolowania w najgorszym przypadku przy 32 bit int i 5 podzialow i 4
rolowania przy 64 bit long.
> >
> > Jak wykonywać te podziały? zwykle przy połowie słowa liczy się tylko to
> > młodsze.
> > czy będzie to tak a wewnątrz procedura inline szukaj_przesuwajac
> > używająca << maksymalnie 4 razy?
> > uint32_t mask
> > if(mask)
> > {
> > if (mask & 0x0000ffff) //16 młodszych
> > {
> > if (mask & 0x000000ff) //8 najmłodszych
> > {
> > if (mask & 0x0000000f) szukaj_przesuwajac
> > else szukaj_przesuwajac
> > }
> > else
> > {
> > if (mask & 0x00000f00) szukaj_przesuwajac
> > else szukaj_przesuwajac
> > }
> > }
> > else
> > {
> > if (mask & 0x00ff0000) //8 najmłodszych
> > {
> > if (mask & 0x000f0000) szukaj_przesuwajac
> > else szukaj_przesuwajac
> > }
> > else
> > {
> > if (mask & 0x0f000000) szukaj_przesuwajac
> > else szukaj_przesuwajac
> > }
> > }
> > }
>
> Tka przy okazji, z czystej ciekawosci sie pytam na jakim systemie to mam byc
implementowane - czy to tylko teoretyczne dewagacje - za wyjatkiem duzych
web-serwerow i baz danych obslugujacych bardzo duze firmy (w tym przypadku sa dobrze
znane rozwiazania jak radzic sobie z problemem) ciezko mi wyobrazic sobie system
ktory uruchamia miliony watkow - nie mowiac juz o milionach zadan.

Może jeden wątek dostaje listę zasobów, potem część z tej listy zwalnia, a
zwolnione powinny pójść do innych/nowych wątków? Może średnio działa 10
wątków i każdy dostaje średnio 200tys numerków?

Pozdrawiam

do góry

W dniu 2015-12-04 o 20:10, Adam M pisze:
> Tka przy okazji, z czystej ciekawosci sie pytam na jakim systemie to mam byc
implementowane - czy to tylko teoretyczne dewagacje - za wyjatkiem duzych
web-serwerow i baz danych obslugujacych bardzo duze firmy (w tym przypadku sa dobrze
znane rozwiazania jak radzic sobie z problemem) ciezko mi wyobrazic sobie system
ktory uruchamia miliony watkow - nie mowiac juz o milionach zadan.

Na Linuxie, zasoby te to akurat nie wątki, ale np. okna i inne.
Chcę oprogramować korzystanie z czystego protokołu X11. Tam gdy chcę
utworzyć okno to wypełniam strukturę i wysyłam do socketu do pliku typu
specjalnego w /tmp. W tej strukturze muszę podać numer uchwytu, a ten
numer wiem, że może być >= numerowi bazowemu i dostępnych jest ok 2 mln
(akurat w mojej konfiguracji). Nie utworzę tyle okien i innych zasobów,
ale gdy będę tworzył i niszczył okno w pętli to nie mogę brać cały czas
najwyższego numeru, musi być recykling.

do góry

On 04.12.2015 15:04, Borneq wrote:
> Każdy zasób określony jest przez numer z zakresu <a,b), bez miany
> ogólności możemy przyjąć że zakres jest <0,n) gdzie n=b-a.
> N jest duże, np. dwa miliony, więc nie ma obaw że zabraknie zasobów, n
> to ilość ile może być zasobów JEDNOCZEŚNIE. Ale gdy zwolnimy jakiś
> zasób, jego numer może zostać przydzielony znowu.
> Choć duże n, to może się skończyć, gdy będziemy przydzielać, zwalniać i
> zwiększać k.
> Są dwie strategie: albo przydzielać zawsze najniższy wolny numer, albo
> cały czas inkrementować k, przydzielać najwyższy numer, aż gdy k
> osiągnie n, wtedy zawinie się od początku. Jak jest lepiej?
> Jaka struktura? Czy trzymać listę raczej wolnych czy raczej zajętych
> numerów? Gdy będzie mało wykorzystane, oszczędniej trzymać raczej listę
> zajętych, ale listę wolnych może lepiej szukać?


Rozumoem, że nie chodzi o obiekt w pamięci. Bo jeśli tak,
to można to zrobić jeszcze sprytniej.

Pomysł wstępny:
Stos wolnych. Gdy wątek pobiera zasób, zabier go jednocześnie
ze stosu. Gdy zwalnie, wsadza numer na samą górę.

Wszystko w czasie stałym.

Modyfikacja: kolejka fifo w cyklicznym buforze (wielkosći N+1).
Pobierasz z jednej strony, oddajesz po drugiej.

Ale nie zawsze warto, jeśli ostatnio używane zasób jest
z jakiś posobów lepszy (co siedzi w buforach) to pierwsza
wersja lepsza.


No, chyba, że zasobem są stałej wielkośći fragmenty pamięći
(obiekty po kilka(set) bajtów). Wtedy robie się to inaczej.

pzdr
bartekltg

do góry

On 04.12.2015 23:30, Borneq wrote:
> W dniu 2015-12-04 o 20:10, Adam M pisze:
>> Tka przy okazji, z czystej ciekawosci sie pytam na jakim systemie to
>> mam byc implementowane - czy to tylko teoretyczne dewagacje - za
>> wyjatkiem duzych web-serwerow i baz danych obslugujacych bardzo duze
>> firmy (w tym przypadku sa dobrze znane rozwiazania jak radzic sobie z
>> problemem) ciezko mi wyobrazic sobie system ktory uruchamia miliony
>> watkow - nie mowiac juz o milionach zadan.
>
> Na Linuxie, zasoby te to akurat nie wątki, ale np. okna i inne.
> Chcę oprogramować korzystanie z czystego protokołu X11. Tam gdy chcę
> utworzyć okno to wypełniam strukturę i wysyłam do socketu do pliku typu
> specjalnego w /tmp. W tej strukturze muszę podać numer uchwytu, a ten
> numer wiem, że może być >= numerowi bazowemu i dostępnych jest ok 2 mln
> (akurat w mojej konfiguracji). Nie utworzę tyle okien i innych zasobów,
> ale gdy będę tworzył i niszczył okno w pętli to nie mogę brać cały czas
> najwyższego numeru, musi być recykling.

No to nie potrzebujesz wcale trzymać wszystkich N numerów.

Jak opisałem poprzednio, kolejka fifo w cyklicznym buforze.
Ale inicjalizowana małą ilośćią liczb na początek.
Jeśli kolejka opustoszje, realokujesz dla niej dwa raz wiekszą
pamieć (tzn powiekszasz vectror, w którym to trzymasz:)
i dodajesz kolejne liczby.

pzdr
bartekltg

do góry

W dniu 2015-12-05 o 00:49, bartekltg pisze:
> Jak opisałem poprzednio, kolejka fifo w cyklicznym buforze.
> Ale inicjalizowana małą ilośćią liczb na początek.
> Jeśli kolejka opustoszje, realokujesz dla niej dwa raz wiekszą
> pamieć (tzn powiekszasz vectror, w którym to trzymasz:)
> i dodajesz kolejne liczby.

Pomysł ciekawy, zwłaszcza to, że jest inicjowana małą ilością liczb na
początek, a potem można zwiększać. Kolejkę FIFO rozumiem jako dwa
indeksy wskazujące na bufor, aby nie trzeba było przemieszczać danych?
Na razie zaangażowałem się w maski potrójnego poziomu - maska maks. 256
bitów, drugiego poziomu miała być 65 K a trzeciego 16 M. To raczej
skomplikowana sprawa, więc, jak będą trudności zrobię powiększające się
FIFO.
Wracając do szukania bitu w słowie:
zrobiłem testy, tam m.in. dwie metody z Uczty Programistów, które
przesuwają kolejno o 18,8,4 i 2 bity. Metoda połówkowania całkowita do
bitu i do czterech bitów; dodałem również dla porządku najoczywistszą
metodę pętli.
Co się okazało: wszystkie mniej więcej w tym samym czasie, a najszybsza
była metoda w pętli: (co dziwne, bo czas miał być proporcjonalny do
liczby bitów a nie logarytmu z nich)
int ntz5_15(unsigned x)
{
int n;
x = ~x & (x - 1);
n = 0;
while (x != 0)
{
n = n + 1;
x = x >> 1;
}
return n;
}
Tutaj jest jeden myk: "x = ~x & (x - 1)" wypełnia bity aż do napotkania
pierwszej jedynki od dołu. Dzięki temu nie trzeba w pętli stosować AND.
W gruncie rzeczy potrzebowałem szukać zer, więc:
int findZero32(uint32_t x)
{
int n;
x = x & (~x - 1);
n = 0;
while (x != 0)
{
n = n + 1;
x = x >> 1;
}
return n;
}
Lecz dla 64 bitów pętla to przesada, więc połówkuję go:
int findZero64(uint64_t x)
{
if ((x | 0xffffffff00000000)!= 0xffffffffffffffff)
return findZero32((uint32_t)x); //this branch must be first
else
return findZero32((uint32_t)(x >> 32)) + 32;
}


Jeszcze o testach: test jednorodny odpada, bo połowa przypadków to były
by pomiędzy 2 miliardy a 4 miliardy. Wybieram więc liczbę jedynek od 1
do trzech, potem dla bitu losuję pozycję od 0 do 31 i ustawiam.

Pozdrawiam

do góry

On Saturday, December 5, 2015 at 12:45:15 AM UTC+1, bartekltg wrote:
> On 04.12.2015 15:04, Borneq wrote:
> > Każdy zasób określony jest przez numer z zakresu <a,b), bez miany
> > ogólności możemy przyjąć że zakres jest <0,n) gdzie n=b-a.
> > N jest duże, np. dwa miliony, więc nie ma obaw że zabraknie zasobów, n
> > to ilość ile może być zasobów JEDNOCZEŚNIE. Ale gdy zwolnimy jakiś
> > zasób, jego numer może zostać przydzielony znowu.
> > Choć duże n, to może się skończyć, gdy będziemy przydzielać, zwalniać i
> > zwiększać k.
> > Są dwie strategie: albo przydzielać zawsze najniższy wolny numer, albo
> > cały czas inkrementować k, przydzielać najwyższy numer, aż gdy k
> > osiągnie n, wtedy zawinie się od początku. Jak jest lepiej?
> > Jaka struktura? Czy trzymać listę raczej wolnych czy raczej zajętych
> > numerów? Gdy będzie mało wykorzystane, oszczędniej trzymać raczej listę
> > zajętych, ale listę wolnych może lepiej szukać?
>
>
> Rozumoem, że nie chodzi o obiekt w pamięci. Bo jeśli tak,
> to można to zrobić jeszcze sprytniej.
No właśnie, dokładnie nie wiadomo do czego to jest potrzebne i trudno
coś doradzić. Ja zrozumiałem, nie wiedzieć czemu, że trzeba podać
najmniejszy wolny i bym zasugerował stertę. Może zrozumiałem tak
dlatego, że nie zdecydował się na ciągłe inkrementowanie long long.
Potem Broneq pisał coś o bezpośrednim programowaniu Xa, więc
najlepsze co można zrobić, to zajrzeć do przykładów - tam zapewne
znajdują się rozwiązania dedykowane i obsługujące różne przypadki
które ciężko z góry przewidzieć, i które mogą się pojawić. Struktura
musi być dostosowana do wszystkich przypadków a nie tylko do
podawania unikalnego id.



> Pomysł wstępny:
> Stos wolnych. Gdy wątek pobiera zasób, zabier go jednocześnie
> ze stosu. Gdy zwalnie, wsadza numer na samą górę.
>
> Wszystko w czasie stałym.
Jeśli jest potrzebny dowolny dostępny, to stos lub kolejka wydają się
najlepsze. Jeśli jakiś dowolny numer, to najlepiej:
get( id_thread ) {
static long long res[max] = {0,1,2,3,4...max-1};
return res[id_thread] += max;
}



> Modyfikacja: kolejka fifo w cyklicznym buforze (wielkosći N+1).
> Pobierasz z jednej strony, oddajesz po drugiej.
>
> Ale nie zawsze warto, jeśli ostatnio używane zasób jest
> z jakiś posobów lepszy (co siedzi w buforach) to pierwsza
> wersja lepsza.
>
>
> No, chyba, że zasobem są stałej wielkośći fragmenty pamięći
> (obiekty po kilka(set) bajtów). Wtedy robie się to inaczej.
Zależy, często w takich przypadkach stos i kolejka też się nadają.



Pozdrawiam

do góry

W dniu 2015-12-04 o 15:04, Borneq pisze:
> Każdy zasób określony jest przez numer z zakresu <a,b), bez miany
> ogólności możemy przyjąć że zakres jest <0,n) gdzie n=b-a.
> N jest duże, np. dwa miliony, więc nie ma obaw że zabraknie zasobów, n
> to ilość ile może być zasobów JEDNOCZEŚNIE. Ale gdy zwolnimy jakiś
> zasób, jego numer może zostać przydzielony znowu.

Zrobiłem, nie myślałem że będzie to takie skomplikowane, dużo pomogła mi
obiektowość C++. Liczy aż 500 linii .cpp i 100 linii .h
Zrobiłem maski bitowe. 256 bitów maski reprezentowane jest przez jeden
bit AND i jeden bit OR na poziomie 1, z kolei te 256 bitów przez jeden
maski AND i OR na poziomie 2.
Ponieważ najwyższy poziom liczy 256 bitów, to maksymalnie struktura może
trzymać 256*256*256 = 16M pozycji.

Na poziomie 0 mamy: (dla uproszczenia - 4 zamiast 256 bitów)
[1111] [1011] [0011] [0000] | [0100] [1111] [1000] [0000] | [0000]
[0000] [0000] [0000] | [1111] [1111] [1111] [1111]

Na poziomie 1 maska AND:
1000 | 0100 | 0000 | 1111
Na poziomie 1 maska OR:
1110 | 1110 | 0000 | 1111

więcej pamięci niż maski mogą zużywać indeksu gdzie indeks =
(wskaźnik,numer), gdzie numer to 1 bajt ale wskaźnik to 4 a nawet 8.
i teraz ciekawe: nie pamiętamy na poziomie 0 tych, dla których są same
jedynki albo same zera, czyli te dla których zarówno na poziomie 1 są
jedynki dla AND i OR jak i zera dla obu, czyli XOR=0.
Pamiętamy tylko te nieliczne, gdzie dla OR jest jedynka a dla AND zero.

on level 1 indices from range(16) only for this: not all 0, not all 1
1,2,4,6
just indices is for set bits od XOR mask:
0110 | 1010 | 0000 | 0000

XOR maski AND i OR będzie 0110 | 1010 | 0000 | 0000
czyli będą istnieć maski rzędu 0 dla indeksów 1,2,4,6
Indeks rzędu 2 podobnie tworzymy z rzędu 1.

Podaję linka, może się przydać:
https://gist.github.com/borneq/0bd3c32e5aec4966a40d

Ta wersja ma jeden mankament, o którym pisałem na grupie C "Destruktor
zachowuje się jakby był niewirtualny"
void yBitmaskHi::releaseAllIndices()
{
for (int i = 0; i < indexCount; i++)
delete indices[i].lowerLevel;
indexCount = 0;
}
nie woła destruktora level1, nie wiem czemu

do góry

W dniu 2015-12-06 o 10:12, Borneq pisze:
> Na poziomie 0 mamy: (dla uproszczenia - 4 zamiast 256 bitów)
> Podaję linka, może się przydać:
> https://gist.github.com/borneq/0bd3c32e5aec4966a40d

Uwaga: mówię o 256 bitach, ale tutaj mamy ustawione na razie #define
BitsToBit 4 do celów debugowania, czyli mamy strukturę 4*4*4

do góry

W dniu 2015-12-06 o 10:12, Borneq pisze:
> Ta wersja ma jeden mankament, o którym pisałem na grupie C "Destruktor
> zachowuje się jakby był niewirtualny"
> void yBitmaskHi::releaseAllIndices()
> {
> for (int i = 0; i < indexCount; i++)
> delete indices[i].lowerLevel;
> indexCount = 0;
> }
> nie woła destruktora level1, nie wiem czemu


Poprawione, destruktory muszą być jawnie oznaczone jako wirtualne i w
dodatku klasa bazowa musi mieć konstruktor wirtualny, choćby pusty.

do góry

On 05.12.2015 09:37, Borneq wrote:
> W dniu 2015-12-05 o 00:49, bartekltg pisze:
>> Jak opisałem poprzednio, kolejka fifo w cyklicznym buforze.
>> Ale inicjalizowana małą ilośćią liczb na początek.
>> Jeśli kolejka opustoszje, realokujesz dla niej dwa raz wiekszą
>> pamieć (tzn powiekszasz vectror, w którym to trzymasz:)
>> i dodajesz kolejne liczby.
>
> Pomysł ciekawy, zwłaszcza to, że jest inicjowana małą ilością liczb na
> początek, a potem można zwiększać. Kolejkę FIFO rozumiem jako dwa
> indeksy wskazujące na bufor, aby nie trzeba było przemieszczać danych?

Tak. W booście jest chyba nawet gotowiec. A jak nie ma, zbudujesz
to na bazie vektor w 10 minut.


> Na razie zaangażowałem się w maski potrójnego poziomu - maska maks. 256
> bitów, drugiego poziomu miała być 65 K a trzeciego 16 M. To raczej
> skomplikowana sprawa, więc, jak będą trudności zrobię powiększające się
> FIFO.

I jaką z tego będzeisz miał korzyść?
Potrzebujesz tam jakiś dodatkowych operacjji, o których nie wiem?

Czasowo jest gorsze.
Pamięćiowo najprawdopoobnij też (ile na raz okien będzie otwartych?),
a te dodatkowe 32 bity chyba nie są takim wqielkim narzutem, skoro
jadna liczba przyopada na okno (bardziej skomplikowaną strukturę).

Nie mówiąc o tym, że trudniejsze do napsiania;-)

pzdr
bartekltg

do góry