[Lisp] Ray tracing

[Lars Brinkhoff]

Kanske inte det mest traditionella användningsområdet för Lisp, men
jag har hackat lite på en ray tracer i Lisp:

Loading Image...

[Lars Brinkhoff]

Post by Lars Brinkhoff
http://lars.nocrew.org/lasr/three-balls-and-a-square.jpg

Tjusigt. Frågan är om inte Paul Graham har startat en trend, för jag
tycker mig minnas att jag har börjat se en hel del ray-tracers i
lisp de senaste åren.

Ingen influens från Paul för min del, även om jag läst hans böcker.
Jag har länge varit intresserad av ray tracing och skrivit några
stycken. Denna gången ville jag prova att skriva i Lisp.

Just nu är den ganska långsam jämfört med motsvarande i C, så det ska
bli intressant att se om det går att komma inom 10% som tumregeln
brukar vara.

Ingen annan som är intresserad av 3D-grafik?

[Elias Mårtenson]

Post by Lars Brinkhoff
Ingen annan som är intresserad av 3D-grafik?

Jag, men raytracing är jag inte så jätteintresserad av. "vanlig"
fuskrendering är enklare. :-)

[Ingvar]

Post by Lars Brinkhoff

Post by Lars Brinkhoff
http://lars.nocrew.org/lasr/three-balls-and-a-square.jpg

Tjusigt. Frågan är om inte Paul Graham har startat en trend, för jag
tycker mig minnas att jag har börjat se en hel del ray-tracers i
lisp de senaste åren.

Ingen influens från Paul för min del, även om jag läst hans böcker.
Jag har länge varit intresserad av ray tracing och skrivit några
stycken. Denna gången ville jag prova att skriva i Lisp.
Just nu är den ganska långsam jämfört med motsvarande i C, så det ska
bli intressant att se om det går att komma inom 10% som tumregeln
brukar vara.
Ingen annan som är intresserad av 3D-grafik?

Lite till husbehov, typ (jag har mest knepat 3D-grafik för Pantzer (och
därifrån till Gamelib)), men något verkade knasa till sig senast jag lekte
runt med koden (inte incheckat i CVS, så andra slipper se traset).

Jag skulle inte ha något emot att kika på din kod, när jag nu lyckas hitta
lite ledig tid (det är MYCKET, nu).

//Ingvar

[Mattias Engdegård]

Post by Lars Brinkhoff
Just nu är den ganska långsam jämfört med motsvarande i
C, så det ska
bli intressant att se om det går att komma inom 10% som tumregeln
brukar vara.

Det vore en imponerande bedrift, i synnerhet om det inte sker på
bekostnad av läsbarhet. Jon Harrops resultat
(http://www.ffconsultancy.com/languages/ray_tracer/) indikerar tyvärr
att det kan vara svårt, men även ett försök kan ju förtjäna aktning.

Om man på rätt sätt utnyttjar att man har kompilatorn tillgänglig vid
körning tillsammans med partialevaluering/specialisering så kan nog
Lisp bli kompetitiv med i stort sett vad som helst (för rätt problem
förstås).

[Lars Brinkhoff]

Post by Mattias Engdegård

det ska bli intressant att se om det går att komma inom 10% [av
motsvarande C-program] som tumregeln brukar vara.

Det vore en imponerande bedrift

Nja, det är vad bra Lispkompilatorer ofta klarar av om man anstränger
sig. I ett test för något år sen trodde jag att jag hade fått till
ett flyttalsintensivt program som var något snabbare än motsvarande
kompilerat med gcc. Sedan la jag till -ffast-math, och då blev
C-programmet ca 10% snabbare.

I västa fall har jag skissat på kod som kompilerar till C, anropar
gcc, läser in objektfilen i Lisp, och automatiskt skapar ett
FFI-gränssnitt till funktionen. Då borde jag få upp hastigheten. :)

Post by Mattias Engdegård
i synnerhet om det inte sker på bekostnad av läsbarhet.

Det innebär ofta att man får lägga till många deklarationer, vilket
förmodligen kan anses minska läsbarheten. Dock tänker jag mig att kan
jag abstrahera bort många sådana detaljer genom ett lämpligt lager med
makron.

Post by Mattias Engdegård
Jon Harrop

Enligt min erfarenhet verkar hans resonemang ofta gå ut på att
presentera en studie av ett litet, begränsat problem, och sedan
applicera resultatet generellt på problem av godtycklig storlek.

Post by Mattias Engdegård
Om man på rätt sätt utnyttjar att man har kompilatorn tillgänglig
vid körning tillsammans med partialevaluering/specialisering så kan
nog Lisp bli kompetitiv med i stort sett vad som helst

Ja, jag hade tänkt utforska just den möjligheten och jag ser något
tillfälle.

[Ingvar]

Post by Lars Brinkhoff

Post by Mattias Engdegård

det ska bli intressant att se om det går att komma inom 10% [av
motsvarande C-program] som tumregeln brukar vara.

Det vore en imponerande bedrift

Nja, det är vad bra Lispkompilatorer ofta klarar av om man anstränger
sig. I ett test för något år sen trodde jag att jag hade fått till
ett flyttalsintensivt program som var något snabbare än motsvarande
kompilerat med gcc. Sedan la jag till -ffast-math, och då blev
C-programmet ca 10% snabbare.
I västa fall har jag skissat på kod som kompilerar till C, anropar
gcc, läser in objektfilen i Lisp, och automatiskt skapar ett
FFI-gränssnitt till funktionen. Då borde jag få upp hastigheten. :)

Post by Mattias Engdegård
i synnerhet om det inte sker på bekostnad av läsbarhet.

Det innebär ofta att man får lägga till många deklarationer, vilket
förmodligen kan anses minska läsbarheten. Dock tänker jag mig att kan
jag abstrahera bort många sådana detaljer genom ett lämpligt lager med
makron.

En hel del, ja. Jag knackade dessutom ihop ett makrolager för att slippa
boxade flyttal, men det visade sig inte göra någon större skillnad (och om det
var skillnad var det långsammare) i det enda fall jag testade den på.

//Ingvar

[Lars Brinkhoff]

Jag knackade dessutom ihop ett makrolager för att slippa boxade
flyttal, men det visade sig inte göra någon större skillnad (och om
det var skillnad var det långsammare) i det enda fall jag testade
den på.

Jasså? I mitt test har jag för mig att det gjorde lite skillnad. Det
var framförallt boxning av returvärdet jag undvek, något i stil med:

;;; Före.
(defun foo/boxed ()
42f0)

;;; Efter.
(deftype box () '(simple-array single-float ()))
(defun foo/unboxed (result)
(declare (box result))
(setf (aref result) 42f0)
nil)

[Ingvar]

Post by Lars Brinkhoff

Jag knackade dessutom ihop ett makrolager för att slippa boxade
flyttal, men det visade sig inte göra någon större skillnad (och om
det var skillnad var det långsammare) i det enda fall jag testade
den på.

Jasså? I mitt test har jag för mig att det gjorde lite skillnad. Det
;;; Före.
(defun foo/boxed ()
42f0)
;;; Efter.
(deftype box () '(simple-array single-float ()))
(defun foo/unboxed (result)
(declare (box result))
(setf (aref result) 42f0)
nil)

fast det där är ju en manuell boxning. :)

Det var iofs det jag gjorde, också, det var (i princip) en wrapper som byggde
symbol-makron, som satte värden i en array av rätt flyttalstyp (och deklarerad
och fin), men jag verkar ha kastat den koden (det var antagligen ett fulhack
på mitt förra jobb, som försvann antingen i en disk-krasch eller aldrig lyftes
av den hårddisken).

//Ingvar

[Mattias Engdegård]

Post by Lars Brinkhoff
Nja, det är vad bra Lispkompilatorer ofta klarar av om man anstränger
sig.

Bra C-kompilatorer klarar av rätt mycket också om man anstränger sig.
Det saknas inte tillämpningar där Lisp är vida överlägset C, men man
skall nog inte överdriva.

Post by Lars Brinkhoff
I västa fall har jag skissat på kod som kompilerar till C, anropar
gcc, läser in objektfilen i Lisp, och automatiskt skapar ett
FFI-gränssnitt till funktionen. Då borde jag få upp hastigheten. :)

Visst, det är ungefär så som FFTW är skrivet förutom att det är gjort
som ett C-bibliotek; Lisp hade dugt utmärkt till en sådan sak.

Post by Lars Brinkhoff
Det innebär ofta att man får lägga till många deklarationer, vilket
förmodligen kan anses minska läsbarheten. Dock tänker jag mig att kan
jag abstrahera bort många sådana detaljer genom ett lämpligt
lager med makron.

Men att man överhuvudtaget skall behöva göra sådant manuellt är ju
inte så lyckat. Typinferens och funktionskloning/specialisering borde
väl kunna eliminera behovet av de flesta deklarationer?
Det skall erkännas att kontroll av vektorindexgränser kan kräva ganska
sofistikerat maskineri i allmänhet.

Post by Lars Brinkhoff

Post by Mattias Engdegård
Jon Harrop

Enligt min erfarenhet verkar hans resonemang ofta gå ut på att
presentera en studie av ett litet, begränsat problem, och sedan
applicera resultatet generellt på problem av godtycklig storlek.

Jag håller absolut inte alltid med honom, men till hans heder hör att
han ofta presenterar konkreta exempel och data och inte bara tycker
till. Det är det inte alla som gör.

[Lars Brinkhoff]

Lars Brinkhoff skrevL

Post by Lars Brinkhoff
Nja, det är vad bra Lispkompilatorer ofta klarar av om man
anstränger sig.

Bra C-kompilatorer klarar av rätt mycket också om man anstränger sig.
Det saknas inte tillämpningar där Lisp är vida överlägset C, men man
skall nog inte överdriva.

Du kanske missförstod mig? När jag skrev "inom 10%" menade jag alltså
att Lispprogrammet skulle ha en körtid som ligger på max 110% av mot-
svarande C-program.

Typinferens och funktionskloning/specialisering borde väl kunna
eliminera behovet av de flesta deklarationer?

Ja, och SBCL-kompilatorns typinferens verkar göra det, fast det finns
nog utrymme för ytterligare förbättringar.

[Cons T Åhs]

Det inneb”r ofta att man fÂr l”gga till mÂnga deklarationer, vilket
f–rmodligen kan anses minska l”sbarheten. Dock t”nker jag mig att kan
jag abstrahera bort mÂnga sÂdana detaljer genom ett l”mpligt
lager med makron.

Men att man –verhuvudtaget skall beh–va g–ra sÂdant manuellt ”r ju
inte s lyckat. Typinferens och funktionskloning/specialisering borde
v”l kunna eliminera behovet av de flesta deklarationer?

Det är det som gör ett språk som SML så väldigt trevligt. Statisk typning via typinferens ger väldigt många fördelar, både vad det gäller utveckling (typinferensen fångar mycket) och läsbarhet (man slipper själv deklarera sina typer).

Att sedan SML inte har en lika vacker syntax som Lisp ligger den förstås i fatet.

Cons

[Lars Brinkhoff]

Post by Cons T Åhs
Det är det som gör ett språk som SML så väldigt trevligt. Statisk
typning via typinferens ger väldigt många fördelar, både vad det
gäller utveckling (typinferensen fångar mycket) och läsbarhet (man
slipper själv deklarera sina typer).
Att sedan SML inte har en lika vacker syntax som Lisp ligger den förstås i fatet.

Du skulle kanske gilla Liskell?

[Lars Brinkhoff]

Sedan dess har jag inte gjort mycket åt det, eftersom det verkade
som om raytracing involverade matematik.

Man kan lugnt säga att det involverar matematik. Geometri, vektorer,
matriser, och för mer avancerade algoritmer: signalbehandling,
integraler, sannolikhetslära, statistik.

Jag, men raytracing är jag inte så jätteintresserad av. "vanlig"
fuskrendering är enklare. :-)

Är det inte roligt med komplicerad rendering? :)

Det är möjligt att raytracing blir vanligare i framtiden, eftersom
sådan rendering har en tidskomplexitet av O(log n) för n trianglar
(eller andra objekt), och vanlig rendering är O(n). Om jag förstått
rätt, jag är inte så insatt i algoritmer för realtidsgrafik.

Jag skulle inte ha något emot att kika på din kod, när jag nu lyckas
hitta lite ledig tid (det är MYCKET, nu).

Visst, men det är ganska trasslig kod.

[Cons T Åhs]

Post by Lars Brinkhoff

Post by Lars Brinkhoff
http://lars.nocrew.org/lasr/three-balls-and-a-square.jpg

Tjusigt. Frågan är om inte Paul Graham har startat en trend, för jag
tycker mig minnas att jag har börjat se en hel del ray-tracers i
lisp de senaste åren.

Ingen influens från Paul för min del, även om jag läst hans böcker.
Jag har länge varit intresserad av ray tracing och skrivit några
stycken. Denna gången ville jag prova att skriva i Lisp.
Just nu är den ganska långsam jämfört med motsvarande i C, så det ska
bli intressant att se om det går att komma inom 10% som tumregeln
brukar vara.
Ingen annan som är intresserad av 3D-grafik?

Jodå. Jag har skrivit Ray tracers i C, SML och Lisp. Den i SML är den mest genomarbetade och blev ganska snabb. Man kan göra mycket roliga saker med closures :-)

Cons

[Lars Brinkhoff]

Post by Cons T Åhs
Jag har skrivit Ray tracers i C, SML och Lisp. Den i SML är den
mest genomarbetade och blev ganska snabb. Man kan göra mycket
roliga saker med closures :-)

Trevligt. Har du använt några intressanta algoritmer? Några lyckade
bilder du kan visa upp?

[Tommy Hallgren]

Har alltid trott att ett statisk typat språk kan klara sig utan taggade värden, men blev förvånad när jag läste om ghc och att de har tags på alla objekt.

För skräpsamlaren antar jag, men ändå, är det inte åtminstone teoretiskt möjligt att vara utan tags i en Haskell-miljö?

Det inneb”r ofta att man fÂr l”gga till mÂnga deklarationer, vilket
f–rmodligen kan anses minska l”sbarheten. Dock t”nker jag mig att kan
jag abstrahera bort mÂnga sÂdana detaljer genom ett l”mpligt
lager med makron.

Men att man –verhuvudtaget skall beh–va g–ra sÂdant manuellt ”r ju
inte s lyckat. Typinferens och funktionskloning/specialisering borde
v”l kunna eliminera behovet av de flesta deklarationer?

Det är det som gör ett språk som SML så väldigt trevligt. Statisk typning via typinferens ger väldigt många fördelar, både vad det gäller utveckling (typinferensen fångar mycket) och läsbarhet (man slipper själv deklarera sina typer).

Att sedan SML inte har en lika vacker syntax som Lisp ligger den förstås i fatet.

Cons


_______________________________________________
Lisp mailing list
***@lisp.se
http://mailman.nocrew.org/cgi-bin/mailman/listinfo/lisp



---------------------------------

Stava rätt! Stava lätt! Yahoo! Mails stavkontroll tar hand om tryckfelen och mycket mer! Få den på http://se.mail.yahoo.com

[Mattias Engdegård]

Post by Tommy Hallgren
Har alltid trott att ett statisk typat språk kan klara sig utan
taggade värden, men blev förvånad när jag läste om ghc och att de har
tags på alla objekt.
För skräpsamlaren antar jag, men ändå, är det inte åtminstone
teoretiskt möjligt att vara utan tags i en Haskell-miljö?

Det har skrivits tagglösa implementationer av statiskt typade språk
(bl.a. olika ML-varianter), och visst har det fördelar. Anledningen
till att O'Caml använder taggar är tvåfald: dels underlättar det för
vissa inbyggda ad hoc-polymorfiska operationer (jämförelser), och dels
gör det skräpsamlaren mätbart snabbare.

Det är en avvägning, men eftersom allokeringar (och därmed
skräpsamlingar) är så vanliga i ML ansågs det vara värt den extra
kostnad som taggning medför. Det skall observeras att O'Camls
kompilator kan optimera bort många taggningsoperationer inuti en
funktion så denna kostnad är inte så stor i praktiken. Det finns
dessutom tagglösa flyttalsarrayer.

Däremot saknar jag ibland möjligheten till oboxade fullordsvärden (32
eller 64 bitar). Den traditionella Lisplösningen är att automatiskt gå
över till bignums när det behövs, men det gör det lite svårare att
optimera heltalshanteringen när man inte statiskt vet om bignum-operationer
krävs.

Ett annat alternativ till taggning är att använda en konservativ
skräpsamlare, men senast jag undersökte så var det inte förenligt med
riktigt höga krav på allokeringsprestanda.