Re: [Algorithms] Complexity of new hardware

[Sebastian S. <seb...@gm...>]

On Sun, Apr 26, 2009 at 5:00 AM, Nicholas "Indy" Ray <ar...@gm...>wrote:

> On Sat, Apr 25, 2009 at 5:01 PM, Rachel Blum <r....@gm...> wrote:
> > Actually, I'm referring to type annotations in Haskell. While they are
> not
> > necessary (the inference works quite well), they allow to generate better
> >  (i.e. faster/shorter) code. I'm looking to extend that into a more
> generic
> > system where you slowly annotate your code as you learn more about the
> > problem at hand.
>
> I ment type annotations to be included in advantages of type
> inference, as I haven't seen a type inferred system without optional
> type annotations. Anyways, as far as my understand goes, type
> annotations provide no runtime performance benefits, but help to
> increase safety of computation, a compile time 'assert' of sorts.


They do actually. Haskell always infers the *most general* type for a
function. Adding a type signature can specialize it giving you faster code
(by avoiding the need for runtime dispatch of any polymorphic functions - if
the compiler knows that the * always refers to integer multiplication, it
can just emit the native honest-to-goodness int multiplication instruction
directly). Also, type signatures can be used to specify explicitly that a
given value should be unboxed in GHC (e.g. Int# is an unboxed int). There
are other annotations which can force strict evaluation (add a ! to the
field of a record type, or the name of a parameter to a function), improving
performance in many cases.

As an aside, the Haskell way is actually great for writing generic code (in
C++ et al you have to do extra work to get generic code, in Haskell you have
to do extra work to specialize it). Also, a little hand-wavey, polymorphism
actually restricts the amounts of valid implementations for a given type
(e.g. a type of a -> a, has precisely one imlementation, id, whereas a type
from Integer -> Integer has an infinite number of implementations), and if
the space of legal implementation is reduced then the space of legal
*incorrect* implementations is too, meaning that with generic code an
incorrect implementation is more likely to give a type error. See the
Girard-Reynolds isomorphism for more, and check out djinn, which given a
(polymorphic) type will "magically" produce an implementation for that
function! Sounds completely magical, I know!



> It's nice to be able to start with more malleable code, and then add
> types later to ensure safety, I understand.


As for Haskell, it is always completely statically, and strongly typed. It
just happens to infer those types for you at compile time, saving you some
typing (no pun intended).


> However I do have quite a bit of experience with XNA/C# and as it
> turns out they have a lot of problems, the performance can be
> problematic, GC isn't always desirable when developing games, The
> large amount of bounds checking can also be problematic. Additionally,
> the nature of being a proprietary language/library vastly limits the
> platforms that can be developed for (Mono does a nice job at running
> C# but XNA is still a Microsoft only sort of thing). Lastly while it
> is possible to call into C/C++ libraries though managed C++, it's
> never very pleasant, and on some platforms it may not be possible at
> all. Depending on the game, these may actually be non-problems. But I
> doubt we will be seeing any AAA titles in XNA/C# very shortly, and I
> doubt that is due to the inertia of the entire industry and C++.


I would suspect that the next gen of consoles will make provisions to run
managed code more efficiently, and in particular mixing and matching between
C/C++ for low level systems, and C# or similar for "everything else". E.g.
on the Xbox 360 JIT:ed code has to run in user mode, which incurs a
performance hit. It would certainly be nice if that wasn't the case (either
if it didn't need to switch, or if the performance hit was smaller).



-- 
Sebastian Sylvan
+44(0)7857-300802
UIN: 44640862