Scheme snadno a rychle - 1. typovy system

2.1.2007 23:05 | Přečteno: 1965× | Programování

v beznem clanku o jazycich by alespon druha kapitola urcite byla o gramatikach a takovych tech vecech. ale necham si ji zatim pro sebe. v jazycich odvozenych od lispu, je rozdil mezi hodnotou a samotnym kodem hodne tesny, tak bych napsal neco o implementaci typu. neni to nic svetoborneho a priznavam, inspirovaneho guile.

tagged union

nema smysl zde budovat nejaky komplexni system datovych typu, i kdyz pravda r5rs jich definuje vicero, mj. pocita i s cisly o libovolne velikosti a presnosti. pro zacatek, z tech beznych si postacime se symboly, celymi cisly, boolovskymi hodnotami a typy pro tvorbu seznamu a neco malo pro praci s kodem. takze zavedeme vyctovy typ:

typedef enum scm_type {
	INT,
	PAIR,
	SYMBOL,
	BOOL,
	NIL,
	VOID
} scm_type;

a zavedeme strukturu, ktera se bude skladat z hodnoty a jejiho typu

typedef struct scm_value {
	scm_type type;
	union {
		int integer;
		int bool;
		char * symbol;
		struct scm_pair {
			struct scm_value * ar;
			struct scm_value * dr;
		} pair;
	} value;
} scm_value;

pravda, nektere hodnoty mohou byt vetsi nez by skutecne mohly byt (kvuli tem dvema pointrumu u typu "pair") na druhou stranu to velice zpohodlnuje praci s takovym typem, takze co vyplytvame na miste, usetrime rychlosti pri praci jednotlivych operaci s touto strukturou.

opravdu to neni zadny zazrak, takze pokud by nekdo lisp nebo scheme videl poprve v zivote a zarazilo ho, ze o neco vyse zminuji typ pro tvorbu seznamu a ve strukture neni. pripomel bych, jak se vlastne takovy seznam tvori. jako typ jsou zde zavedny dva prvky a to NIL (prazdny seznam) a PAIR (teckovy par -- promenna obsahuje prave dve hodnoty libovolneho typu. casto se to znaci napr. (1 . 2)) vytvorit z nej seznam je pak docela trivialni zalezitost a to skladanim jednotlivych teckovych paru dohramady v principu (hodnota . seznam), napr. (1 . (2 . (3 . (4 . ())))) pro bezny zapis je to, ale hodne neprakticke, proto se to zkracuje do tvaru (1 2 3 4)

finta s pointrama

na jednu stranu jsem predchvilkou mlel neco o efektivite a mistu, presto tu musim zminit jeden hezky hack, ktery dokaze prijemne zlepsit vykon. pri tvorbe hodnot se pokazde alokuje nove misto v pameti. u typu jako NIL nebo BOOL to jde osetrit zadefinovanim urcitych konstant a z nich si vybirat hodnoty. to jde udelat pokud je hodnot malo, ale co takova cisla? hodnoty 0, 1, -1 jsou docela caste, takze co tak zavest konstanty i pro ne, ale 2 muze byt taky docela caste, atd., atd.

na nekterych architekturach jde pouzit bezva finta, pomalu jak bezva finta, jeana paula belmonda z filmu bezva finta. staci drobna informace o tom, ze vetsina alokatoru alokuje pamet do bloku zarovnanych na 4 nebo 8 bytu. to znamena ze minimalne spodni dva bity jsou vzdy 0 a prakticky se nepouzivaji. cela pointa pak tkvi v tom, ze je pouzijeme jako priznak, jestli se jedna o ukazatel, nebo je v hodnote ulozena nejaka dalsiho informace. napr. pokud je spodni bit nastaven na 0 jedna se o pointer a jako s takovym s nim budeme pracovat, je-li spodni bit 1 jedna se o cele cislo a na zbylych 31 bitech mame ulozenou jeho hodnotu. v kodu to pak vypada nejak takto:

#define scm_value_new_int(__val) ((scm_value *)(1 | ((__val) << 1)))
#define SCM_INT(x)      (int)((long)x >> 1)

makro scm_value_new_int(x) vytvori "ukazatel", ktery vlastne neni ukazatel, ale pouze ciselna hodnota a makro SCM_INT(x) umi hodnotu z tohoto "ukazatele" vycist zpet.

       

Komentáře

[Kyosuke]

Čeština očividně nepokročila, ale obsah přijímám s nadšením. Ty časté hodnoty mi připomínají některé optimalizace ve Smalltalku: bajtkód ST-80 definuje operace (mapcar #'(lambda (x) (concatenate 'string "push " x)) '("true" "false" "-1" "0" "1" "2")) jako samostatné opkódy.

[Kyosuke]

Oprava, v seznamu mi samozřejmě chybí ještě hodnota "nil".

[Kyosuke]

A mimochodem, tagované hodnoty mi nepřijdou jako „hack“, to je technika stará snad jako Metuzalém. A kdyby to používala třeba Java, mohla by mít objektový inty a nemusela by se vymlouvat na výkon.

[podlesh]

To je těžké, určitá sorta lidí by tomu stejně nevěřila... a tatáž sorta lidí by pradvěpodobně nepřekousla 31-bitový celočíselný typ.

[Ladicek]

To se mi líbí. Mohli bychom mít datový typ přirozené číslo s obvyklou horní mezí

[Kyosuke]

No jo, já vím, lidi zapomněli i na šesti-, sedmi- a devítibitový bajty. Lidi zapomenou na leccos.

[zde]

Python tu optimalizaci krátkých integerů kupodivu nepoužívá. Ruby i Lua ano. Sice to šetří paměť, ale komplikuje kód, a Guido asi naznal že bude mít raději integery (a vlastně všechno) důsledně jako reference. Mít všude výhybku na integerovou aritmetiku totiž není žádná sranda- fakticky je třeba samostatně implementovat 31-bitovou aritmetiku a 32-bitovou aritmetiku, a po každém pitomém inkrementu testovat, jestli 32-bit výsledek vleze do 31-bit short intu, nebo ne. Sice se šetří paměť, ale na runtime to má režii.

Taky je zajímavý koukat na jazyky, jestli mají unikátní stringy (Python ani Ruby je nemá, Lua ano). Komplikují se trochu stringové operace, po každém concat nebo substr se výsledek musí znovu atomizovat, ale výhodou je pak velmi rychlé srovnávání stringů na rovnost, a rychlé indexování stringy v hashích (ekvivalence obsahu implikuje identickou referenci).

A když už mluvíte o fintách s tagovanými krátkými integery, proč nezmínit taky geniální fintu zvanou BBOP? Prakticky každý lepší malloc() ji interně používá, aby si zapamatoval jak velký je alokovaný blok, aniž by size musel ukládat na jeho začátek. Když jde do vysokých bitů pointeru ukládat velikost bloku, jde tam samozřejmě ukládat i typetag.

Bohužel nevím o žádném sysému, který by to dělal. Smalltalk?

[zde]

Hmm, tak jsem googlil, a není to BBOP, ale BIBOP. A BIBOP pro typetagy se občas používají, např. the Icon programming language.

[Kyosuke]

„…a po každém pitomém inkrementu testovat, jestli 32-bit výsledek vleze do 31-bit short intu, nebo ne. Sice se šetří paměť, ale na runtime to má režii.“

A u short integeru se v Pythonu netestuje, jestli se výsledek vleze zase do short integeru nebo se musí vytvořit long? Jinak, Ruby 2.0 bude po vzoru Smalltalku Symbol mít jako podtřídu Stringu (na rozdíl od současné implementace), takže je klidně možné, že se bude chovat stejně.

A ten tzv. BBOP je čirou náhodou vynález Lispu z poloviny sedmdesátých let.

[zde]

A u short integeru se v Pythonu netestuje

Python 31-bit short integery nemá. Má normální 32-bit integery (signed, immutable, na heapu, často používané hodnoty zamknuté ve sdílené tabulce), a pak má long integery (signed, mutable, na heapu, bignum). Lua myslím nic jiného než 31-bit short integery, kódované do referencí, nemá. Je to pak krásně jednoduché :) Perl je superhnusosračka, ten integery neumí vůbec, všechno snad počítá v double nebo co, a bit shifty se mu chovají naprosto nepředvídatelně.

Symbol mít jako podtřídu Stringu

Haha. Lua vládne. Hash je list, a list je hash. String je symbol, a symbol je string.

BBOP je čirou náhodou vynález Lispu z poloviny sedmdesátých let.

Není, Lisp měl zones. Co to je nevím, ale když se tomu říká jinak, tak to bude něco jiného :)

[Kyosuke]

„Python 31-bit short integery nemá. Má normální 32-bit integery (signed, immutable, na heapu, často používané hodnoty zamknuté ve sdílené tabulce), a pak má long integery (signed, mutable, na heapu, bignum).“

Reagoval jsem na tvrzení, že se něco musí testovat a má to režii. V Pythonu přetékají short integery do long integerů a tudíž se tam asi něco testuje, jinak by se to nemohlo chovat jinak v závislosti na tom, jestli to přeteče nebo ne. Asi mi něco ušlo.

„Není, Lisp měl zones. Co to je nevím, ale když se tomu říká jinak, tak to bude něco jiného :)“

Doporučuju přečíst si Data Representations in PDP-10 MACLISP, autor Guy Steele Jr., MIT 1977. Občas je dobré vědět a ne si jen myslet. Cestu ke Googlu určitě znáš.

[zde]

FOLDOC sayez:

This idea is similar to the "zones" used in some Lisp systems (e.g. LeLisp).

Protože vím že mezi "similar" a "identical" je podstatný rozdíl, nic hledat nebudu.

[Kyosuke]

Tak moment. Já netvrdím, že zones jsou totéž a BiBoP – nejsou. Ale to, že zones jsou něco jiného, ještě neimplikuje, že BiBoP není vynález autorů MACLISPu.

[zde]

Přece se nebudem hádat o tom kdo si první všiml které zjevné věcí, jako že reference i hodnoty mají stejnou podstatu, a že jednoduchý alokátor má zbytečně mnoho stupňů volnosti. Unikátní objevy neexistují, prvenství je irelevantní, vše je nezávislý důsledek slepé indukce smíchané s okamžikem náhodné inspirace. Já taky vymyslel BSP stromy rok a půl předtím, než jsem o nich četl první odborný článek, a nedělám z toho vědu, protože téměř určitě to předtím v nějaké zapomenuté gamesce udělal i někdo jiný.. Když existuje zadání a prostředí, řešení je samozřejmé.

[Kyosuke]

No to je mi rétorika. Tak nejdřív taková vehementní reakce na moje konstatování, že BIBOP je vynálezem z Lispu (zčásti stimulované větou „bohužel nevím o žádném systému, který by to dělal“ ) a najednou se nebudeme hádat. Já se nehádám, nemám proč – pouze prezentuji fakta, nikoli vágní představy o historii. Přinejmenším název BiBoP pochází přímo z mnou odkazované práce. Což je další (a ještě závažnější) důvod, proč jsem ji vytáhnul na světlo. Existuje-li několik příbuzných konceptů, pochopitelně nemá vůbec smysl nějaký konkrétní název vytahovat, ovšem já s ním v téhle diskusi nepřišel.

[Kyosuke]

Jo a kdybych chtěl být fakt tvrdý, připomenul bych, že existují-li příbuzné koncepty, mezi kterými je třeba rozlišovat, aby nedošlo ke zmatení, pak tasit se s BiBoPem v kontextu GC a zjišťování velikosti alokovaných bloků je velmi nešťastné, poněvadž BiBoP slouží výhradně k úspoře paměti potřebné k ukládání objektů, a to v souvislosti s potřebou odvodit nějakým způsobem typ objektu z reference. BiBoP není schopný říct, jaká je velikost objektů, jako je třeba array nebo hunk. Fixní velikosti objektů na stránce jsou nad rámec BiBoPovy pracovní smlouvy.

[zde]

Velikost instance je normální součást metadat. Rozlišovat odvození typu objektu z reference, a odvození jeho velikosti z téhož proto nemá smysl, leda byste byl pedagog.

[Kyosuke]

Normální součástí metadat, hm. Jenže průšvih je třeba v tom, že pole mohou mít různou velikost. A BIBOP nemá speciální stránky pro „pole velikosti 42“. (K čemu sloužil, o tom jsem už psal.) Respektive může mít, v konkrétní implementaci, ale není to jeho povinnost. Každopádně přeju hodně štěstí při vynalézání kola.

Mimochodem, ten název stejně zůstal nepochopený. Ono to „Big Bag of Pages“ označovalo mezeru operačního systému ITS, která se nacházela mezi částí fyzické paměti určené pro texty programů (která v tomto operačním systému rostla směrem nahoru) a přidělovanými datovými stránkami (které v něm přibývaly směrem dolů). Holt si někdo pomíchal pojmy a začal nazývat způsob organizace objektů do stránek a zjišťování jejich typů názvem, který se týkal pouze toho, odkud se nově alokované ztránky získávaly. Ale to jen taková historická douška.

[deda.jabko]

ono resit 31-bitu pretekajicich na 32 neni zase takove velke dilema, ve scheme se treba musi jeste kontrolovat jestli vysledne cislo nepretece mimo definovany typ a pokud ano, pak prevest na nejaky bignum typ (nejspis pomoci libgmp)... ale to nevim, jestli budu resit....

to s tema sdilenama stringama muze mit taky neco do sebe... pri pouziti na symboly... kdyz si clovek uvedomi, ze symboly se opakuji skoro porad dokola -- to je same lambda, define, cons, list, let,... na druhou stranu to zapleveli kod parseru, ale problemy se substr a concat odpadaji... jeste o tom popremyslim....

abych pravdu rekl o BiBoP jsem nevedel, finta je to moc pekna, ale ma jednu chybu -- potrebuje napsat cely memory managment pomalu na zelene louce, takze pro zatim bych ji vyloucil jako predcasnou optimalizaci ;-]

[zde]

Pokud budete chtít mít dobrý GC, je memory management na zelené louce téměř nutnost. Poslední rok taky uvažuju, že napíšu vlastní skriptovací jazyk. Vypadá to na runtime (datový model, hashe, closury, GC) založené na LUA, syntaxí a objekty z Pythonu (s přídaným auto i explicitním statickým typováním, ale bez MI, ala Java), s custom memory managerem, BEZ bytecode vrstvy (jen přímý nerelokovatelný i386 backend, něco z GNU Lightning, něco z TinyCC). Memory manager bude BBOP, na začátku stránky budou immutable metadata (typetagy, classinfo, unit size, atd), na konci stránky pak alokační bitmapa instancí. Krom toho bude ještě jedna bitmapa pro zcela volné stránky (arena bude mít pevnou velikost). Žádné generace, žádné inkrementální GC, jen jednoduchý mark & sweep GC, optimalizovaný pro velké množství transientních dat (předpokládám že při běhu GC bude většina stránek free + dirty), takže se stránky jen zahodí, a GC bude zapisovat jen do bitmapy stránek.

[deda.jabko]

tak to si tak pul roku vyclente jenom na ten memory managment. ;-]

jak jsem psal v predchozim clanku, neberte to jako nejake fundamentalni cteni, spis jako demonstraci ze jde jednoduse napsat interpretr plnohodnotneho jazyka na par set radek.

[zde]

tak to si tak pul roku vyclente jenom na ten memory managment. ;-]

Zrovna tohle je věc, kterou jsem měl dotaženou nejdál, a částečně implementovanou. Zajímala mě primárně rychlost alokace, tak jsem to benchmarkoval oproti mallocu(). Vyladěný hodinový alokátor, ukusující z úplně nové stránky, byl jen zhruba o 40% rychlejší než malloc(). To mě tehdy vážně nasralo, hrál jsem si tam s asm/bitops.h, nasekal tam fůru likely() na horký cesty, 31 alokací z 32 mělo být jen pár lineárních instrukcí, kód z gcc vypadal fakt dobře.. a ono to při minimální funkcionalitě bylo jen o fous rychlejší než libc. Čekal jsem naivně řádovej rozdíl, tohle mě fakt zklamalo, dal jsem to k ledu.

jak jsem psal v predchozim clanku, neberte to jako nejake fundamentalni cteni, spis jako demonstraci ze jde jednoduse napsat interpretr plnohodnotneho jazyka na par set radek.

Bezva, těším se.

[deda.jabko]

prave s memory managmentem jsem si taky hral (se zamerenim na paralelni prostredi), proti libc to bylo fakt o neco rychlejsi, ale pak jsem zkusil jine alokatory a pomyslny uspech byl ten tam... a vzhledem k tomu, ze beohmuv gc podava podobne vykony jako libc malloc, ktery pouziva vetsina aplikaci, nebylo co resit.... (ta divocina s atomickymi operacemi za to fakt nestoji)

[Tom.š Ze.le.in]

Mít všude výhybku na integerovou aritmetiku totiž není žádná sranda- fakticky je třeba samostatně implementovat 31-bitovou aritmetiku a 32-bitovou aritmetiku, a po každém pitomém inkrementu testovat, jestli 32-bit výsledek vleze do 31-bit short intu, nebo ne. Sice se šetří paměť, ale na runtime to má režii

Ne nezbytně - nevím jak scheme (asi ne), ale některé Common Lispy jsou ochotny uvěřit deklaracím že vše je fixnum (tedy 31-bitový integer) a generovat efektovní kód - tedy pokud o tu runtime režii až tak jde....

* (declaim (optimize speed space (safety 0) (debug 0)))
* (defun plus (a b)
   (declare (fixnum a b))
   (the fixnum (+ a b)))
PLUS
* (disassemble #'plus)

; 0A5F1A0E:       01FA             ADD EDX, EDI
;       10:       8D65F8           LEA ESP, [EBP-8]
;       13:       F8               CLC
;       14:       8B6DFC           MOV EBP, [EBP-4]
;       17:       C20400           RET 4
;       1A:       90               NOP
;       1B:       90               NOP
;       1C:       90               NOP
;       1D:       90               NOP
;       1E:       90               NOP
;       1F:       90               NOP
; 
NIL

[Kyosuke]

„…nevím jak scheme (asi ne)…“

Stalin by k tomu určitě šel dokopat.

[zde]

Hmm, žrádýlko.