Dědičnost dnes

[ava]

Jenom pro ujasneni, n je mnozstvi pameti, ktere mas k dispozici (protoze RAM je konecna), a pod RAM myslim vsude Random Access Memory.

Předpokládám, že velikost paměti počítače je konstantní. Ani nevěřím tomu, že rychlost přístupu do paměti závisí na její velikosti. Určitě je rozdíl v rychlosti přístupu do cache a dohlavní paměti, ale to se nedá popsat takto jednoduše.

Bohužel je to čistá realita, sám jsem na to narazil před pár měsíci při implementaci kolaborativního filtru pro větší data (řádově GB v RAM)

Tady jsou výsledky JMH benchmarku, který testuje zápis na náhodná místa různě velkých polí, vždy milion zápisů ve (stejně) náhodném pořadí. Ve sloupečcích jsou

- velikost cílového pole
- Kolikrát se podařilo milionkrát zapsat do cílového pole za 3 vteřiny
- Jak dlouho trvá zápis miliónu položek.


             1  3898   0.769 ± 0.003  ms/op
             2  3967   0.756 ± 0.003  ms/op
             4  3882   0.773 ± 0.003  ms/op
            32  3929   0.763 ± 0.003  ms/op
           256  3974   0.754 ± 0.003  ms/op
           512  3912   0.767 ± 0.004  ms/op
          1024  3927   0.764 ± 0.003  ms/op
          2048  3986   0.752 ± 0.003  ms/op
          4096  3985   0.752 ± 0.002  ms/op
          8192  3993   0.751 ± 0.002  ms/op
         16384  3990   0.751 ± 0.004  ms/op
         65536  2278   1.318 ± 0.013  ms/op
       1048576  1094   2.741 ± 0.060  ms/op
       4194304  872   3.440 ± 0.089  ms/op
       8388608  480   6.268 ± 0.120  ms/op
      16777216  357   8.426 ± 0.158  ms/op
      33554432  316   9.533 ± 0.132  ms/op
      67108864  295  10.210 ± 0.102  ms/op
     134217728  275  10.954 ± 0.120  ms/op
     536870912  238  12.686 ± 0.343  ms/op
    1073741824  185  16.323 ± 0.680  ms/op

Je vidět, že rychlost vykonávání "algoritmu" na velikosti dat závisí poměrně významně. Zajímavé také je, že takovýhle "algoritmus" nad velkými daty na jednom počítači skoro nejde paralelizovat, protože bottleneck je přístup do RAM.

Pro úplnost



sudo dmidecode -t cache
# dmidecode 3.0
Getting SMBIOS data from sysfs.
SMBIOS 2.8 present.

Handle 0x0003, DMI type 7, 19 bytes
Cache Information
   Socket Designation: L1 Cache
   Configuration: Enabled, Not Socketed, Level 1
   Operational Mode: Write Back
   Location: Internal
   Installed Size: 64 kB
   Maximum Size: 64 kB
   Supported SRAM Types:
      Synchronous
   Installed SRAM Type: Synchronous
   Speed: Unknown
   Error Correction Type: Parity
   System Type: Data
   Associativity: 8-way Set-associative

Handle 0x0004, DMI type 7, 19 bytes
Cache Information
   Socket Designation: L1 Cache
   Configuration: Enabled, Not Socketed, Level 1
   Operational Mode: Write Back
   Location: Internal
   Installed Size: 64 kB
   Maximum Size: 64 kB
   Supported SRAM Types:
      Synchronous
   Installed SRAM Type: Synchronous
   Speed: Unknown
   Error Correction Type: Parity
   System Type: Instruction
   Associativity: 8-way Set-associative

Handle 0x0005, DMI type 7, 19 bytes
Cache Information
   Socket Designation: L2 Cache
   Configuration: Enabled, Not Socketed, Level 2
   Operational Mode: Write Back
   Location: Internal
   Installed Size: 512 kB
   Maximum Size: 512 kB
   Supported SRAM Types:
      Synchronous
   Installed SRAM Type: Synchronous
   Speed: Unknown
   Error Correction Type: Single-bit ECC
   System Type: Unified
   Associativity: 4-way Set-associative

Handle 0x0006, DMI type 7, 19 bytes
Cache Information
   Socket Designation: L3 Cache
   Configuration: Enabled, Not Socketed, Level 3
   Operational Mode: Write Back
   Location: Internal
   Installed Size: 4096 kB
   Maximum Size: 4096 kB
   Supported SRAM Types:
      Synchronous
   Installed SRAM Type: Synchronous
   Speed: Unknown
   Error Correction Type: Multi-bit ECC
   System Type: Unified
   Associativity: 16-way Set-associative

[Reklama]

[ava]

Jo, "položkou" myslím jeden bajt

[javaman ()]

Nejen typy. Nic se mi nemění. Závislosti jsou napevno. Kód metod je pevný. Žádná reflexe, žádné dynamické vychytávky. Nic, prostě všechno je jasně dané tak, jak jsem to navrhl.

Jediné dynamické jsou data z venku. Což ale právě ten můj systém nemůže rozbít, protože vše je jasně definované.

Nebo mi něco uniká?

[javaman ()]

A čo si, Kefalín, predstavujete pod takým slovom "dynamický"?

Že všechno je dané při spuštění aplikace. Nic se mi nemění. Pokud se něco mění, tak za pevně definované hodnoty, které jsem znal při spuštění (změna konfigurace). Takže to lze i otestovat. Všechno ostatní mi přijde jako takové hraní na vývoj. Možná ale právě tu vaši dynamičnost nechápu dobře...

Tak teď jsem lehce na pochybách, zda rozumíte alespoň té Javě...

Já už taky

[zboj]

Jenom pro ujasneni, n je mnozstvi pameti, ktere mas k dispozici (protoze RAM je konecna), a pod RAM myslim vsude Random Access Memory.

Předpokládám, že velikost paměti počítače je konstantní. Ani nevěřím tomu, že rychlost přístupu do paměti závisí na její velikosti. Určitě je rozdíl v rychlosti přístupu do cache a dohlavní paměti, ale to se nedá popsat takto jednoduše.

Bohužel je to čistá realita, sám jsem na to narazil před pár měsíci při implementaci kolaborativního filtru pro větší data (řádově GB v RAM)

Tady jsou výsledky JMH benchmarku, který testuje zápis na náhodná místa různě velkých polí, vždy milion zápisů ve (stejně) náhodném pořadí. Ve sloupečcích jsou

- velikost cílového pole
- Kolikrát se podařilo milionkrát zapsat do cílového pole za 3 vteřiny
- Jak dlouho trvá zápis miliónu položek.


             1  3898   0.769 ± 0.003  ms/op
             2  3967   0.756 ± 0.003  ms/op
             4  3882   0.773 ± 0.003  ms/op
            32  3929   0.763 ± 0.003  ms/op
           256  3974   0.754 ± 0.003  ms/op
           512  3912   0.767 ± 0.004  ms/op
          1024  3927   0.764 ± 0.003  ms/op
          2048  3986   0.752 ± 0.003  ms/op
          4096  3985   0.752 ± 0.002  ms/op
          8192  3993   0.751 ± 0.002  ms/op
         16384  3990   0.751 ± 0.004  ms/op
         65536  2278   1.318 ± 0.013  ms/op
       1048576  1094   2.741 ± 0.060  ms/op
       4194304  872   3.440 ± 0.089  ms/op
       8388608  480   6.268 ± 0.120  ms/op
      16777216  357   8.426 ± 0.158  ms/op
      33554432  316   9.533 ± 0.132  ms/op
      67108864  295  10.210 ± 0.102  ms/op
     134217728  275  10.954 ± 0.120  ms/op
     536870912  238  12.686 ± 0.343  ms/op
    1073741824  185  16.323 ± 0.680  ms/op

Je vidět, že rychlost vykonávání "algoritmu" na velikosti dat závisí poměrně významně. Zajímavé také je, že takovýhle "algoritmus" nad velkými daty na jednom počítači skoro nejde paralelizovat, protože bottleneck je přístup do RAM.

Pro úplnost



sudo dmidecode -t cache
# dmidecode 3.0
Getting SMBIOS data from sysfs.
SMBIOS 2.8 present.

Handle 0x0003, DMI type 7, 19 bytes
Cache Information
   Socket Designation: L1 Cache
   Configuration: Enabled, Not Socketed, Level 1
   Operational Mode: Write Back
   Location: Internal
   Installed Size: 64 kB
   Maximum Size: 64 kB
   Supported SRAM Types:
      Synchronous
   Installed SRAM Type: Synchronous
   Speed: Unknown
   Error Correction Type: Parity
   System Type: Data
   Associativity: 8-way Set-associative

Handle 0x0004, DMI type 7, 19 bytes
Cache Information
   Socket Designation: L1 Cache
   Configuration: Enabled, Not Socketed, Level 1
   Operational Mode: Write Back
   Location: Internal
   Installed Size: 64 kB
   Maximum Size: 64 kB
   Supported SRAM Types:
      Synchronous
   Installed SRAM Type: Synchronous
   Speed: Unknown
   Error Correction Type: Parity
   System Type: Instruction
   Associativity: 8-way Set-associative

Handle 0x0005, DMI type 7, 19 bytes
Cache Information
   Socket Designation: L2 Cache
   Configuration: Enabled, Not Socketed, Level 2
   Operational Mode: Write Back
   Location: Internal
   Installed Size: 512 kB
   Maximum Size: 512 kB
   Supported SRAM Types:
      Synchronous
   Installed SRAM Type: Synchronous
   Speed: Unknown
   Error Correction Type: Single-bit ECC
   System Type: Unified
   Associativity: 4-way Set-associative

Handle 0x0006, DMI type 7, 19 bytes
Cache Information
   Socket Designation: L3 Cache
   Configuration: Enabled, Not Socketed, Level 3
   Operational Mode: Write Back
   Location: Internal
   Installed Size: 4096 kB
   Maximum Size: 4096 kB
   Supported SRAM Types:
      Synchronous
   Installed SRAM Type: Synchronous
   Speed: Unknown
   Error Correction Type: Multi-bit ECC
   System Type: Unified
   Associativity: 16-way Set-associative

To je pořád O(1).

[Reklama]

[ava]

Ještě pardon, ten prostřední sloupeček asi ignorujte, důležitý je ten poslední, doba vykonání...

[noef]

Já jsem požadoval konkrétní implementaci konkrétního algoritmu, v konkrétním FP jazyku bez side efektů, která po překladu vygeneruje pro reálný HW stejně efektivní kód (stačí z hlediska asymptotické složitosti) jako implementace v imperativním jazyku.

Moc nechapu, proc by kdokoliv mel pristoupit na ten zakaz necistych knihoven. Dokud maji FP ciste rozhrani a chovani z vnejsku, tak nevidim zadny problem v jejich uzivani. Take bezne nevidim zakazovani pouzivani C knihoven z Javy proto, ze to neni "Java OOP".

Přijde mi, že Zboj, Prýmkem a vy máte své náboženství a snažíte se ho obhajovat za každou cenu. Když náhodou nemáte pravdu, tak protivníka ubijete argumentem "to v praxi není rozhodující" nebo naopak pseudointelektuálními žvásty (ty používá hlavně zboj) a citací vašich FP guruů.

Proto napr. pan Prymek nekolikrat psal, ze FP se nehodi na vse .

[gll]

Jenom pro ujasneni, n je mnozstvi pameti, ktere mas k dispozici (protoze RAM je konecna), a pod RAM myslim vsude Random Access Memory.

Předpokládám, že velikost paměti počítače je konstantní. Ani nevěřím tomu, že rychlost přístupu do paměti závisí na její velikosti. Určitě je rozdíl v rychlosti přístupu do cache a dohlavní paměti, ale to se nedá popsat takto jednoduše.

Bohužel je to čistá realita, sám jsem na to narazil před pár měsíci při implementaci kolaborativního filtru pro větší data (řádově GB v RAM)

to je závislost na množství paměti využívané vaším programem, ne na velikosti paměti počítače. Pochybuji, že jste během testu přidával paměť. IMHO je to způsobeno tím, že při zvětšování velikosti toho pole se snižuje pravděpodobnost, že trefíte adresu v cache. Asi to není O(log(n)), ale něco jako O(1-1/n).

[ava]

To je pořád O(1).

Doba vykonání pro algoritmus "milionkrát zapiš 1 na náhodné místo v paměti" v uvedeném příkladě je O(log(N)), kde N je velikost cílového pole.

[zboj]

Tedy realna RAM neni O(1), ale spis O(log n), a takovou RAM lze realizovat i funkcionalne (pomoci stromu).

Tak to určitě neplatí. Čas přístupu do paměti neroste logaritmicky s velikostí vstupu programu. O(1) je jen horní odhad rychlosti operace. Stačí uvažovat nejpomalejší možný přístup. Pořád to bude reálnému hardwaru mnohem blíž než Turingův stroj.

Jenom pro ujasneni, n je mnozstvi pameti, ktere mas k dispozici (protoze RAM je konecna), a pod RAM myslim vsude Random Access Memory.

Jde mi o to, ze bud chces teoreticky dokazat, ze FP je vypocetne horsi - pak ano, mas pravdu, neumoznuje O(1) pristup do pameti. Jenze v praxi O(1) pristup neumoznuje nic, zadne zarizeni (jinak receno, kazde fyzikalni zarizeni bude pomalejsi pokud bude dostatecne velke).

Nebo se chces bavit o praktickych aspektech implementace FP, a pak nemusime nutne trvat na tom, aby vysledny program (strojovy kod) byl funkcionalne cisty, protoze FP pouzivame jen jako abstrakci pro popis, nikoli jako vypocetni model.

Takze at se snazis dokazat cokoli z toho, pro praxi to neni rozhodujici.

Pokud chceme slovíčkařit, tak FP neumožňuje přístup do paměti vůbec, protože žádnou nemá, když jsou vše jen funkce. Gll absolutně neví, o čem mluví, zápis funkcí v FP nevypovídá zhola nic o jejich výpočetní složitosti (ani o tom, jestli jsou vůbec vyhodnotitelné), protože si plete pojmy algoritmus a (matematická) funkce. Doporučuju nereagovat na něj, dokud se nedoučí alespoň elementární definice (aspoň - jak píšete - formální popis a výpočetní model). Dokud to nezvládne, bude pořád diskutovat na úrovni aspiranta zvláštní školy...

[zboj]

To je pořád O(1).

Doba vykonání pro algoritmus "milionkrát zapiš 1 na náhodné místo v paměti" v uvedeném příkladě je O(log(N)), kde N je velikost cílového pole.

Složitost operace milionkrát zapiš je zcela jasně O(n). O(1) je přístup do paměti.

[ava]

Jenom pro ujasneni, n je mnozstvi pameti, ktere mas k dispozici (protoze RAM je konecna), a pod RAM myslim vsude Random Access Memory.

Předpokládám, že velikost paměti počítače je konstantní. Ani nevěřím tomu, že rychlost přístupu do paměti závisí na její velikosti. Určitě je rozdíl v rychlosti přístupu do cache a dohlavní paměti, ale to se nedá popsat takto jednoduše.

Bohužel je to čistá realita, sám jsem na to narazil před pár měsíci při implementaci kolaborativního filtru pro větší data (řádově GB v RAM)

to je závislost na množství paměti využívané vaším programem, ne na velikosti paměti počítače. Pochybuji, že jste během testu přidával paměť. IMHO je to způsobeno tím, že při zvětšování velikosti toho pole se snižuje pravděpodobnost, že trefíte adresu v cache. Asi to není O(log(n)), ale něco jako O(1-1/n).

Jo, to jo, na celkové velikosti RAM to nezáleží, a paměť se za běhu nepřidává, jestli tu něko něco takového tvrdil, tak to bude spíše nějaké zmatení. Samozřejmě že je to kvůli cachím (proto jsem je dole uvedl), a podle mě to vychází na O(log(n)).

[gll]

To je pořád O(1).

Doba vykonání pro algoritmus "milionkrát zapiš 1 na náhodné místo v paměti" v uvedeném příkladě je O(log(N)), kde N je velikost cílového pole.

to není. Jestli je to způsobené jen pravděpodobností cahce hitů, tak ta závislost bude 1-1/n což je to stejné co O(1)

[lopata]

Jediné dynamické jsou data z venku. Což ale právě ten můj systém nemůže rozbít, protože vše je jasně definované.

Nebo mi něco uniká?

Uniká ti tohle: https://en.wikipedia.org/wiki/Halting_problem

[ava]

To je pořád O(1).

Doba vykonání pro algoritmus "milionkrát zapiš 1 na náhodné místo v paměti" v uvedeném příkladě je O(log(N)), kde N je velikost cílového pole.

Složitost operace milionkrát zapiš je zcela jasně O(n). O(1) je přístup do paměti.

Ještě jednou si přečti, co píšu. Věta "Složitost operace milionkrát zapiš je zcela jasně O(n)" nedává smysl, nepíšeš, co je pro tebe n. Pokud jsi tím n myslel "milion", tak to taky nedává smysl, protože milion je v tomhle případě konstanta a ne parametr.