Rychlost Chez Scheme

Coati

Rychlost Chez Scheme
« kdy: 21. 12. 2022, 18:24:31 »
Může někdo vysvětlit, jak autoři Chez Scheme dosahují rychlosti srovnatelné s Céčkem/Rustem u tohoto jazyka? Intuitivně bych u dynamického jazyka čekal určitou režii (za dynamické typování a vysokoúrovňové abstrakce).


Re:Rychlost Chez Scheme
« Odpověď #1 kdy: 25. 12. 2022, 00:12:44 »
zrovna scheme není zrovna nějak složitý a nebo velmi vysokourovnovy jazyk :D Podívej se na revised 6 /7 scheme report.

Idris

  • *****
  • 2 286
    • Zobrazit profil
    • E-mail
Re:Rychlost Chez Scheme
« Odpověď #2 kdy: 25. 12. 2022, 00:40:48 »
zrovna scheme není zrovna nějak složitý a nebo velmi vysokourovnovy jazyk
Proč je teda rychlý jen Chez (a svého času Stalin)? Tam zjevně směřovala otázka, že je Scheme poměrně jednoduchý se obecně ví.

Re:Rychlost Chez Scheme
« Odpověď #3 kdy: 25. 12. 2022, 04:03:06 »
Chez Scheme kompiluje do nativního kódu, ale just-in-time a díky typové inferenci se té dynamicity může zbavit. A někdy tato strategie vyústi v rychlejší program než C nebo Rust protože je k dispozici více kontextu, ale to se nestává příliš často.

Idris

  • *****
  • 2 286
    • Zobrazit profil
    • E-mail
Re:Rychlost Chez Scheme
« Odpověď #4 kdy: 25. 12. 2022, 06:09:51 »
Chez Scheme kompiluje do nativního kódu, ale just-in-time a díky typové inferenci se té dynamicity může zbavit. A někdy tato strategie vyústi v rychlejší program než C nebo Rust protože je k dispozici více kontextu, ale to se nestává příliš často.
Ano, tohle je správná odpověď. Navíc pokud se například generuje kód ve Scheme z nějakého typovaného jazyka a ví se tedy, že typy jsou na 100% správně, jde typová kontrola za běhu explicitně vypnout.


Re:Rychlost Chez Scheme
« Odpověď #5 kdy: 25. 12. 2022, 12:52:00 »
Zkusím trochu střelby od pasu.

Otázka je, co přesně znamená „dosahují rychlosti srovnatelné s Céčkem/Rustem“. Věřím, že bude existovat nějaký benchmark, který tak dopadl. Třeba u nějaké funkce, která má na vstupu i výstupu číslo (z hlediska dynamicky typovaného jazyka tam ale může přijít cokoliv), se může vyplatit udělat specializovanou variantu, která bude číslo předpokládat, a v některých případech ji použít – například dynamicky zkontrolovat předpoklad, že je na vstupu číslo, a podle toho se rozhodnout mezi obecnou a specializovanou variantou. Tady věřím, že se může podařit prakticky odstranit režii dynamicky typovaného jazyka, zvlášť pokud výpočet v té funkci bude náročnější, a tedy režie s kontrolou na začátku funkce bude zanedbatelná.

Podobné věci bych čekal spíše u JIT, který může využít informace z běhu (funkce f dostane vždy int, funkce g int nebo float, funkce h dostane v 99 % případů int), nicméně i AOT (ahead of time) to může udělat, jen k tomu má méně informací.

Pokud bychom ale měli funkci, která bude intenzivně pracovat s košatou strukturou, může být s podobnou optimalizací problém. Ono už u obyčejného pole může být náročné dtnamicky zjistit typ všech jeho prvků – jednak by to typicky znamenalo projít všechny prvky a jednak bychom mohli mít problém v případě úpravy pole třeba z jiného vlákna. Navíc je těžké podobná pole efektivně reprezentovat – v obecném případě je přímočaré udělat pole pointerů na hodnoty prvků, protože nepředpokládám konkrétní typy. Pro pole integerů se nabízí udělat přímo pole integerů (a nemít žádné pointery), ale pokud nemohu zajistit, že se tam nedostane prvek jiného typu, potřebuju řešení pro případ, že se tam nějak dostane. Což může být u velkého pole časově náročné. Ano, lze mít typy jako Int32Array, které nic jiného nepřijmou, ale tím v podstatě dodávám trochu typové informace ručně.

A teď si představte, že nemáte homogenní pole různé strukturované heterogenní hashmapy, které s odkazují na další hashmapy, atd. S dynamickým typováním to bude celkem běžné, třeba v JS objektový literál {key: value, …} je v podstatě taková heterogenní hashmapa.

Idris

  • *****
  • 2 286
    • Zobrazit profil
    • E-mail
Re:Rychlost Chez Scheme
« Odpověď #6 kdy: 25. 12. 2022, 14:36:37 »
Zkusím trochu střelby od pasu.

Otázka je, co přesně znamená „dosahují rychlosti srovnatelné s Céčkem/Rustem“. Věřím, že bude existovat nějaký benchmark, který tak dopadl. Třeba u nějaké funkce, která má na vstupu i výstupu číslo (z hlediska dynamicky typovaného jazyka tam ale může přijít cokoliv), se může vyplatit udělat specializovanou variantu, která bude číslo předpokládat, a v některých případech ji použít – například dynamicky zkontrolovat předpoklad, že je na vstupu číslo, a podle toho se rozhodnout mezi obecnou a specializovanou variantou. Tady věřím, že se může podařit prakticky odstranit režii dynamicky typovaného jazyka, zvlášť pokud výpočet v té funkci bude náročnější, a tedy režie s kontrolou na začátku funkce bude zanedbatelná.

Podobné věci bych čekal spíše u JIT, který může využít informace z běhu (funkce f dostane vždy int, funkce g int nebo float, funkce h dostane v 99 % případů int), nicméně i AOT (ahead of time) to může udělat, jen k tomu má méně informací.

Pokud bychom ale měli funkci, která bude intenzivně pracovat s košatou strukturou, může být s podobnou optimalizací problém. Ono už u obyčejného pole může být náročné dtnamicky zjistit typ všech jeho prvků – jednak by to typicky znamenalo projít všechny prvky a jednak bychom mohli mít problém v případě úpravy pole třeba z jiného vlákna. Navíc je těžké podobná pole efektivně reprezentovat – v obecném případě je přímočaré udělat pole pointerů na hodnoty prvků, protože nepředpokládám konkrétní typy. Pro pole integerů se nabízí udělat přímo pole integerů (a nemít žádné pointery), ale pokud nemohu zajistit, že se tam nedostane prvek jiného typu, potřebuju řešení pro případ, že se tam nějak dostane. Což může být u velkého pole časově náročné. Ano, lze mít typy jako Int32Array, které nic jiného nepřijmou, ale tím v podstatě dodávám trochu typové informace ručně.

A teď si představte, že nemáte homogenní pole různé strukturované heterogenní hashmapy, které s odkazují na další hashmapy, atd. S dynamickým typováním to bude celkem běžné, třeba v JS objektový literál {key: value, …} je v podstatě taková heterogenní hashmapa.
V Chezu se dá kontrola typů za běhu explicitně vypnout.

Re:Rychlost Chez Scheme
« Odpověď #7 kdy: 25. 12. 2022, 14:57:20 »
To ale řeší rychlost jen částečně. Ano, máte-li funkci přijímající parametr jediného typu, můžete zde něco ušetřit za cenu problémů, když předpoklad není naplněn.

IIRC ve Scheme třeba funkce + může pracovat s celými, desetinnými nebo komplexními čísly*. Každé z nich má jinou binární reprezentaci. Můžeme tedy mít funkci, která bude brát více typů. Kompilátor může pro některé typy udělat rychlejší specializovaný kód, a pak se podle typu rozhodnout (třeba i za běhu), který kód použije. Ale tuto kontrolu odstraníte stěží, pokud chcete zachovat optimalizaci…

*) Výčet nemusí být kompletní.

Idris

  • *****
  • 2 286
    • Zobrazit profil
    • E-mail
Re:Rychlost Chez Scheme
« Odpověď #8 kdy: 25. 12. 2022, 14:59:49 »
To ale řeší rychlost jen částečně. Ano, máte-li funkci přijímající parametr jediného typu, můžete zde něco ušetřit za cenu problémů, když předpoklad není naplněn.
To se dělá v případě nějaké externí typové kontroly, takže předpoklad je naplněn vždy.

Idris

  • *****
  • 2 286
    • Zobrazit profil
    • E-mail
Re:Rychlost Chez Scheme
« Odpověď #9 kdy: 20. 01. 2023, 22:37:25 »
autoři Chez Scheme dosahují rychlosti srovnatelné s Céčkem/Rustem
Nově ověřeno na novém projektu :) Klobouk dolů :D

Re:Rychlost Chez Scheme
« Odpověď #10 kdy: 21. 01. 2023, 08:00:12 »
autoři Chez Scheme dosahují rychlosti srovnatelné s Céčkem/Rustem
Nově ověřeno na novém projektu :) Klobouk dolů :D

Mohla by být nějaká ukázka pls? Jde mi o to, jaký "level" abstrakce ten kód má, jestli to třeba jen nění "prekabátěné céčko" (nic ve zlém, ale třeba na https://benchmarksgame-team.pages.debian.net/benchmarksgame/index.html je vidět, jak lidi ohýbají řešení až do extrému jen proto, aby z nějakého jazyka dostali další % speedupu). Fakt mě to zajímá, zrovna u Scheme.

Ink

  • *****
  • 664
    • Zobrazit profil
    • E-mail
Re:Rychlost Chez Scheme
« Odpověď #11 kdy: 21. 01. 2023, 09:16:37 »
autoři Chez Scheme dosahují rychlosti srovnatelné s Céčkem/Rustem
Nově ověřeno na novém projektu :) Klobouk dolů :D

Mohla by být nějaká ukázka pls? Jde mi o to, jaký "level" abstrakce ten kód má, jestli to třeba jen nění "prekabátěné céčko" (nic ve zlém, ale třeba na https://benchmarksgame-team.pages.debian.net/benchmarksgame/index.html je vidět, jak lidi ohýbají řešení až do extrému jen proto, aby z nějakého jazyka dostali další % speedupu). Fakt mě to zajímá, zrovna u Scheme.

U těchto jazyků je hlavní problém v syntaxi - Lisp je slepá ulička, kterou (skoro) nikdo fakt chodit nechce. Tu abstrakci si tam představit dovedu, ale za jakou cenu...

Re:Rychlost Chez Scheme
« Odpověď #12 kdy: 21. 01. 2023, 09:55:59 »
U těchto jazyků je hlavní problém v syntaxi - Lisp je slepá ulička, kterou (skoro) nikdo fakt chodit nechce. Tu abstrakci si tam představit dovedu, ale za jakou cenu...

Muzes dat nejakej priklad problemu v syntaxi Lispu?

Ja se netajim tim, ze mi to vyhovuje a furt nedokazu pochopit co na tom komu muze vadit....
OK oteviraci zavorku pisu na trochu jiny misto nez v jinych jazycich, ale na to se prece snadno da zvyknout.
A vyhody ktery to prinasi jsou obrovske... homoikonicita, structured editing, nemusim resit priority operatoru ...

Idris

  • *****
  • 2 286
    • Zobrazit profil
    • E-mail
Re:Rychlost Chez Scheme
« Odpověď #13 kdy: 21. 01. 2023, 11:57:31 »
autoři Chez Scheme dosahují rychlosti srovnatelné s Céčkem/Rustem
Nově ověřeno na novém projektu :) Klobouk dolů :D
Mohla by být nějaká ukázka pls? Jde mi o to, jaký "level" abstrakce ten kód má, jestli to třeba jen nění "prekabátěné céčko" (nic ve zlém, ale třeba na https://benchmarksgame-team.pages.debian.net/benchmarksgame/index.html je vidět, jak lidi ohýbají řešení až do extrému jen proto, aby z nějakého jazyka dostali další % speedupu). Fakt mě to zajímá, zrovna u Scheme.
Scheme je jen cíl transpilace, ten kód je dost nečitelný a plný lambd, podobný guláš jako výsledek překladu TS nebo Javy (GWT) do JS. Výchozí kód je čistě funkcionální (à la Haskell), do C má hodně daleko :)

Idris

  • *****
  • 2 286
    • Zobrazit profil
    • E-mail
Re:Rychlost Chez Scheme
« Odpověď #14 kdy: 21. 01. 2023, 12:01:04 »
U těchto jazyků je hlavní problém v syntaxi - Lisp je slepá ulička, kterou (skoro) nikdo fakt chodit nechce. Tu abstrakci si tam představit dovedu, ale za jakou cenu...
Muzes dat nejakej priklad problemu v syntaxi Lispu?

Ja se netajim tim, ze mi to vyhovuje a furt nedokazu pochopit co na tom komu muze vadit....
OK oteviraci zavorku pisu na trochu jiny misto nez v jinych jazycich, ale na to se prece snadno da zvyknout.
A vyhody ktery to prinasi jsou obrovske... homoikonicita, structured editing, nemusim resit priority operatoru ...
Samozřejmě tam žádný problém není, jen praktické výhody. Subjektivní preference jsou jiná věc.

Když už by se mělo kritizovat, tak spíše sémantiku, například typová dynamičnost, ale i na to jsou řešení (přinejmenším dvě).