Optimization of dynamic languages...

http://steve-yegge.blogspot.com/2008/05/dynamic-languages-strike-back.html

-- 
Darren New / San Diego, CA, USA (PST)

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> http://steve-yegge.blogspot.com/2008/05/dynamic-languages-strike-back.html

  With all the talk about fancy new languages which are so super-efficient
and so super-fast and so super-secure and whatever, I not seen too much
discussion about one thing: What about dynamically loadable libraries?

  Most of these people boast how their favorite programming language is
able to create cold fusion and solve world hunger in 0.1 seconds, yet
they usually are running their programs written in that language on an
OS which is completely based on libc and dynamically loadable libraries
to do the low-level stuff efficiently.

  Most of what I have seen of these languages, especially the dynamic
ones, seems to be completely incompatible with DLLs.

  It seems to me that everybody has completely forgotten or, more probably,
misunderstood the idea behind DLLs. When someone sees the acronym "DLL"
the only thing he can think of is the so-called "DLL hell" in Windows,
where your system directories are completely bloated with DLL files, with
all their dependency problems and such. In the unix side of the world,
with the DLL equivalents, ie. the .so files, it's more like they sit
there and that's it. They are not a bother, but nobody thinks why they
exist in the first place either.

  DLL files in Windows don't exist because Microsoft got some fancy but
braindead idea and decided to impose it on everyone. .so files in unix
systems don't exist just because of the fun of it. They have a purpose.

  The idea behind DLL files is to save memory: The vast majority of
programs use the exact same libraries. For example in linux almost 100%
of programs (regardless of the language they are written in) use libc,
plus a bunch of others. In Windows the figure is probably something
similar.

  The amount of programs running at any given time can be counted in
the hundreds. The OS starts all kinds of processes and services just to
boot up. Every single one of them uses the exact same libc library, plus
a bunch of other common libraries. Given that libc is rather large, it
would be an enormous waste of memory if each single process would load
it for itself. If I'm not mistaken, libc is something like 2MB in size.
Multiply that by a couple hundred of processes.

  The idea with dynamically loadable libraries is that they are loaded
only *once* into memory, and every running program which needs that
library uses that *one* instance of it. This means that even if you
have a couple hundred of processes running, libc is still only loaded
once into memory, requiring only that 2MB of RAM. Every single process
uses that one single libc instance.

  Programming languages which have absolutely no support for dynamically
loadable libraries are riding on libc and the other libraries which the
OS directly supports. Without this system they would be hopeless memory
hogs. You wouldn't be able to build and entire OS created with that
programming language only. You *need* dynamically loadable libraries
for the system to work.

  It just feels that people who advocate fancy languages just ignore
this fact: They are dependent on an efficient dynamically loadable
library system (almost always created with C), but they completely
ignore the fact, and instead diss C as if it was a pestilence. They
completely fail to explain how the system could work if they did not
have that pestilent C system below, running the system.

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
>   Most of what I have seen of these languages, especially the dynamic
> ones, seems to be completely incompatible with DLLs.

I don't follow. Both Java and .NET are basically 100% dynamically 
loaded. Javascript and Python and such are also 100% dynamically loaded.

>   DLL files in Windows don't exist because Microsoft got some fancy but
> braindead idea and decided to impose it on everyone. .so files in unix
> systems don't exist just because of the fun of it. They have a purpose.

Heh. I'm not sure why you think Microsoft and Unix have different 
approaches to this. The only mistake Microsoft made was to have the 
version number inside the DLL rather than part of the name of the DLL. 
What lead to "DLL Hell" is two people updating the same system DLL with 
incompatible bugs.  Solved via the DLL Cache and side-by-side installs, 
which is basically what UNIX does with .so's. I can't tell you how often 
I've had to make a symlink from /usr/lib/libyadda.1.3.7.so to 
/usr/lib/libyadda.1.3.8.so to make a compiled program run. So both 
approaches have their flaws. :-)

>   The amount of programs running at any given time can be counted in
> the hundreds. The OS starts all kinds of processes and services just to
> boot up. Every single one of them uses the exact same libc library, plus
> a bunch of other common libraries. Given that libc is rather large,

I suspect the amount of libc used by any particular program is somewhat 
smaller, tho. The new Microsoft "Singularity" OS even inlines bits of 
the kernel into your application - stuff like allocating pages of memory 
doesn't even leave the subroutine doing it, let alone trap out.

> You wouldn't be able to build and entire OS created with that
> programming language only. You *need* dynamically loadable libraries
> for the system to work.

Check out the Singularity OS. Real live working OS, with one of the 
fundamental assumptions being that once you start a process, *nothing* 
in the executable can change. No dynamic loading, no plug-ins, etc.

>   It just feels that people who advocate fancy languages just ignore
> this fact: They are dependent on an efficient dynamically loadable
> library system (almost always created with C), but they completely
> ignore the fact, and instead diss C as if it was a pestilence. They
> completely fail to explain how the system could work if they did not
> have that pestilent C system below, running the system.

I don't think that's what this lecture is about. It's about making the 
run-time (and IDEs for that matter) of dynamic systems as efficient as 
the run-time of static systems. For example, how do you inline calls to 
a DLL even in a language like C? What if the overhead for calling the 
floating point library in libc[1] is greater than the actual time used 
to do the floating point ops?

[1] Remember - not all machines have floating point built in. Even the 
8086 had the 8087 as optional.

-- 
Darren New / San Diego, CA, USA (PST)

Post a reply to this message

Warp <war### [at] tagpovrayorg> wrote:
> completely fail to explain how the system could work if they did not
> have that pestilent C system below, running the system.

How does that "C system below" -- which is actually machine code below -- would
work without hardware below, running the system?  How would java programs run
without the JVM?

Come on!  There must always be something low-level there upon which we build
things up.  It's surely important, but it doesn't mean we got to be always at
that level... I enjoy being at the top, quite entertaining a view... :)

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> Warp wrote:
> >   Most of what I have seen of these languages, especially the dynamic
> > ones, seems to be completely incompatible with DLLs.

> I don't follow. Both Java and .NET are basically 100% dynamically 
> loaded. Javascript and Python and such are also 100% dynamically loaded.

  It's not a question of whether it's dynamically loaded or not. It's
a question of whether programs which are running at the same time and
share a library use only one instance of that library, or is that library
loaded separately for both programs.

  There may be speed optimization advantages when loading the library on
a per-application basis, but at the cost of enormously increased memory
consumption. If you have a couple of hundreds of programs using the same
big library, if the library is loaded for every single one of them, the
system will require huge amounts of extra RAM.

> >   The amount of programs running at any given time can be counted in
> > the hundreds. The OS starts all kinds of processes and services just to
> > boot up. Every single one of them uses the exact same libc library, plus
> > a bunch of other common libraries. Given that libc is rather large,

> I suspect the amount of libc used by any particular program is somewhat 
> smaller, tho. The new Microsoft "Singularity" OS even inlines bits of 
> the kernel into your application - stuff like allocating pages of memory 
> doesn't even leave the subroutine doing it, let alone trap out.

  Loading a dynamically loadable library does not change the program being
executed (other than it's told where the functions it wants to call are
located).

  Inlining kernel code into the application makes sense only if that
doesn't increase the memory footprint of the application considerably.
If 2MB of kernel code would be inlined into each single application which
is run, that would be madness. The amount of apps running in a typical OS
is quite large, usually in the hundreds.

> > You wouldn't be able to build and entire OS created with that
> > programming language only. You *need* dynamically loadable libraries
> > for the system to work.

> Check out the Singularity OS. Real live working OS, with one of the 
> fundamental assumptions being that once you start a process, *nothing* 
> in the executable can change. No dynamic loading, no plug-ins, etc.

  Does that mean that every application has all the system libraries
statically linked to them, and this system library code exists in all
of them and are loaded into memory for all of them?

  Memory hogging to the max.

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
> completely fail to explain how the system could work if they did not
> have that pestilent C system below, running the system.

Oh, and btw, download that there Singularity OS. Note the almost 
complete lack of anything remotely approaching C in the source. The use 
of C in Singularity is approximately like the use of assembler in 
C-based operating systems - the stuff that's impossible to do in the 
higher-level languages, like turning interrupts into appropriate stack 
frames and saving off registers during context switches.

That was one of the premises they started with: what if nothing in the 
OS was written in a language like C? :-)

-- 
Darren New / San Diego, CA, USA (PST)

Post a reply to this message

nemesis <nam### [at] gmailcom> wrote:
> How does that "C system below" -- which is actually machine code below -- would
> work without hardware below, running the system?  How would java programs run
> without the JVM?

  The difference is that nobody disses the hardware (ok, they do, but in a
different way) or the JVM, but they diss C.

-- 
                                                          - Warp

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> That was one of the premises they started with: what if nothing in the 
> OS was written in a language like C? :-)

  They will still need dynamically loadable libraries for the system to
be rational.

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
>   It's not a question of whether it's dynamically loaded or not. It's
> a question of whether programs which are running at the same time and
> share a library use only one instance of that library, or is that library
> loaded separately for both programs.

I would think the read-only parts of the code could certainly be shared. 
There's no good reason why things like Java .class files couldn't be 
loaded into shared memory.

>   There may be speed optimization advantages when loading the library on
> a per-application basis, but at the cost of enormously increased memory
> consumption. If you have a couple of hundreds of programs using the same
> big library, if the library is loaded for every single one of them, the
> system will require huge amounts of extra RAM.

Yep. Altho I would think you would need to actually measure how much of 
the shared code is actually used and shared in modern applications.

>   Loading a dynamically loadable library does not change the program being
> executed (other than it's told where the functions it wants to call are
> located).

Um, yes, it does. Sure. There's places you can branch to after loading 
the code that you couldn't branch to before.

Or, to put it another way, say you have a C++ class, and nowhere in any 
of your code do you reference the public integer field "xyz" that's in 
that class. (Including nowhere do you invoke any methods of the class 
that reference xyz.) The compiler Singularity uses would simply not 
allocate space for that field in any of the classes. Now, if you 
dynamically loaded code and passed it an instance of that class that 
*did* reference the field, you'd be broken.

So, yes, dynamically loading code changes the executable *process*.

>   Inlining kernel code into the application makes sense only if that
> doesn't increase the memory footprint of the application considerably.

Right. You'd have to measure it. Welcome to time/space tradeoffs. ;-)

>> Check out the Singularity OS. Real live working OS, with one of the 
>> fundamental assumptions being that once you start a process, *nothing* 
>> in the executable can change. No dynamic loading, no plug-ins, etc.
> 
>   Does that mean that every application has all the system libraries
> statically linked to them, and this system library code exists in all
> of them and are loaded into memory for all of them?

Depends on what you consider to be "system library code". The system is 
broken into a large number of small processes. So there isn't really a 
whole lot of "system library code" going on there. Stuff like "open()" 
isn't in the kernel, so it's not really a library. The runtime is linked 
in staticall, yes.

Each process does have its own garbage collector, but that's good 
because each process can use a different garbage collector, depending on 
the types of garbage it collects.

I think one of the things they're looking at is indeed shared-memory 
libraries, but I don't think they've gone very far in that direction.

It did, yes, seem somewhat wasteful, and it's a research project, so 
they may not be too worried about it.  But I can't think of any 
theoretical reason why having large blocks of executable code being 
shared amongst multiple processes would be especially difficult in 
Singularity. They just haven't done it yet.

-- 
Darren New / San Diego, CA, USA (PST)

Post a reply to this message

Warp <war### [at] tagpovrayorg> wrote:
> nemesis <nam### [at] gmailcom> wrote:
> > How does that "C system below" -- which is actually machine code below -- would
> > work without hardware below, running the system?  How would java programs run
> > without the JVM?
>
>   The difference is that nobody disses the hardware (ok, they do, but in a
> different way) or the JVM, but they diss C.

They would if they were told to program in assembly or bytecode.

Post a reply to this message

Warp wrote:
> Darren New <dne### [at] sanrrcom> wrote:
>> That was one of the premises they started with: what if nothing in the 
>> OS was written in a language like C? :-)
> 
>   They will still need dynamically loadable libraries for the system to
> be rational.

It's possible. I suppose it also depends on (a) how much memory they 
think they'll have in machines by the time it's actually a production 
OS, and (b) what markets they're targetting.

Certainly for general desktop or server systems, you might have dozens 
of non-trivial applications running at once. In contrast, I think the 
first target environment for Singularity is something akin to TiVo, or 
Media Center, where you really don't have someone with dozens of windows 
open at once.

But sure, I can see the system evolving to put something like the 
native-code regexp library in a dedicated page of address space, loading 
it on demand, and sharing it with all the different programs that use 
that library. Or, you could just have a "regexp server" where you send 
the strings you want parsed and it returns you the results. This 
wouldn't have a whole lot more overhead than simply calling it directly, 
since you're sharing address space with the regexp server itself. It's 
not like it would have the IPC overhead it would in Windows or Linux or 
something.

-- 
Darren New / San Diego, CA, USA (PST)

Post a reply to this message

Darren New wrote:

> Oh, and btw, download that there Singularity OS. Note the almost 
> complete lack of anything remotely approaching C in the source. The use 
> of C in Singularity is approximately like the use of assembler in 
> C-based operating systems - the stuff that's impossible to do in the 
> higher-level languages, like turning interrupts into appropriate stack 
> frames and saving off registers during context switches.

Or, alternatively, House, which is a mixture of Haskell and assembly. 
(It contains 0% C.)

Of course, there's no software to run on it (unless it's written in 
Haskell - oh wait, I already said "no software", I'm repeating myself), 
and it's a highly experimental research prototype, not a production OS. 
And honestly, I doubt it'll ever be a production OS either...

Lots of very cool stuff like using the type system to ensure that 
hardware registers are accessed in the correct way, etc., but who's 
gonna use it?

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Orchid XP v8 wrote:
> Lots of very cool stuff like using the type system to ensure that 
> hardware registers are accessed in the correct way, etc., but who's 
> gonna use it?

Yeah, singularity does this with its device drivers too. Pretty cool, 
ensuring at compile time that your kernel-mode device driver doesn't 
step on anything else. :-)

-- 
Darren New / San Diego, CA, USA (PST)

Post a reply to this message

Darren New wrote:
> Orchid XP v8 wrote:
>> Lots of very cool stuff like using the type system to ensure that 
>> hardware registers are accessed in the correct way, etc., but who's 
>> gonna use it?
> 
> Yeah, singularity does this with its device drivers too. Pretty cool, 
> ensuring at compile time that your kernel-mode device driver doesn't 
> step on anything else. :-)

Heh - do you remember back when a "data type" was just a thing to tell 
the compiler how many bits to allocate any whether to include the sign 
bit during comparisons? ;-)

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Warp wrote:

>   With all the talk about fancy new languages which are so super-efficient
> and so super-fast and so super-secure and whatever, I not seen too much
> discussion about one thing: What about dynamically loadable libraries?

GHC [currently the best Haskell compiler] used to be able to compile 
DLLs. At some point that code path bitrotted and stopped working; I'm 
not sure what the current status is.

According to the old documentation, it used to be a case of throwing a 
commond line switch, and your compiled program would call DLL versions 
of the Haskell libraries rather than being statically linked to them. 
You don't change any Haskell code, it's just a compiler switch.

Needless to say, if you have a few dozen Haskell programs, not having a 
dozen copies of the Prelude is something of a win. (!)

I'll see if I can figure out what the current status of this feature 
is... I'm curios myself.

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> Each process does have its own garbage collector, but that's good 
> because each process can use a different garbage collector, depending on 
> the types of garbage it collects.

  But doesn't that make each program selfish? In other words, it only takes
care of itself not running out of memory but completely disregards any other
program running in the system at the same time?

-- 
                                                          - Warp

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> Certainly for general desktop or server systems, you might have dozens 
> of non-trivial applications running at once. In contrast, I think the 
> first target environment for Singularity is something akin to TiVo, or 
> Media Center, where you really don't have someone with dozens of windows 
> open at once.

  In a typical modern OS there may be hundreds of processes running even
if the system has just booted up and the user has not started any program
of his own. There are all kinds of drivers, services, task managers,
window managers, firewalls... you name it. Every single one of them uses
the same system libraries (eg. typically libc plus a few others in linux).

  Just because the user has not started any program doesn't mean there
isn't a big bunch of programs running.

-- 
                                                          - Warp

Post a reply to this message

Orchid XP v8 <voi### [at] devnull> wrote:
> GHC [currently the best Haskell compiler] used to be able to compile 
> DLLs. At some point that code path bitrotted and stopped working; I'm 
> not sure what the current status is.

  I faintly remember asking about this subject in the other group once.
I think it was about how Haskell manages (or if it manages at all) to
create precompiled (possibly dynamically-loadable) libraries which
nevertheless work with any user-defined type and user-defined functions.

  In object-oriented programming this is typically achieved with dynamic
binding (ie. virtual functions): The precompiled library doesn't need
to know the user-defined type as long as it has been inherited from a
base class defined in the library. The virtual table attached to objects
of that class allows the precompiled library to call the proper user-defined
function. (In a way you could say that the user code is telling the library
which function to call for each of the virtual functions in the base class.)

  However, how does haskell manage to do this? Suppose you have something
like this precompiled into a dynamically loadable library:

foldl1 (+) someList

  Also assume the user has defined his own element type for the list and
the (+) function for that element type, and then calls the dynamically
loaded library by giving it a list with elements of that type. How does
the library know which (+) function to call? How does it know that a (+)
function exists for that element type in the first place?

-- 
                                                          - Warp

Post a reply to this message

"Warp" <war### [at] tagpovrayorg> wrote in message 
news:48d92c0d@news.povray.org...
> Darren New <dne### [at] sanrrcom> wrote:
>> http://steve-yegge.blogspot.com/2008/05/dynamic-languages-strike-back.html
>
>  With all the talk about fancy new languages which are so 
> super-efficient
> and so super-fast and so super-secure and whatever, I not seen 
> too much
> discussion about one thing: What about dynamically loadable 
> libraries?

dlls make portable software hard.

Post a reply to this message

Warp wrote:
> Darren New <dne### [at] sanrrcom> wrote:
>> Each process does have its own garbage collector, but that's good 
>> because each process can use a different garbage collector, depending on 
>> the types of garbage it collects.
> 
>   But doesn't that make each program selfish? In other words, it only takes
> care of itself not running out of memory but completely disregards any other
> program running in the system at the same time?

Yes? And how is that different from, say, Windows or Linux? Maybe I'm 
not understanding your point.

I don't think I've ever written a program for Windows or Linux and 
worried about how much memory other processes in the system might be 
using at the moment. I think I did exactly one program like that on the 
Amiga. Not that I intentionally used more memory than I needed, mind.

What I was describing in that quote is this: The real-time programs use 
a real-time GC, the interactive programs use an interactive GC. It 
really doesn't have too much to do with how *much* memory they use.

Obviously if you have your memory management hardware turned off, you're 
going to have a hard time doing demand paging of stuff off the disk, but 
systems worked with that restriction for years and years. And they have 
mechanisms in place to let you turn that on for particular programs that 
want it, IIRC.

-- 
Darren New / San Diego, CA, USA (PST)

Post a reply to this message

Warp wrote:
>   In a typical modern OS there may be hundreds of processes running even
> if the system has just booted up and the user has not started any program
> of his own. There are all kinds of drivers, services, task managers,
> window managers, firewalls... you name it. Every single one of them uses
> the same system libraries (eg. typically libc plus a few others in linux).

I understand that. How much of libc is actually used in common by a 
majority of those programs? What sorts of things do you think are in 
libc that's used by all the programs, other than (let's see) I/O and 
perhaps the floating point stuff (which probably isn't used by too many 
device drivers, task managers, or firewalls :-).

In any case, like I said, there are possibilities in that system that 
you could have libraries like that available at certain shared physical 
addresses if you wanted, or being set up as services in their own 
process, for large discrete-functionality packages. Indeed, this is just 
exactly how the kernel itself is set up.  They just don't do it for 
other packages, yet, as far as I know.

>   Just because the user has not started any program doesn't mean there
> isn't a big bunch of programs running.

Yes. And far more in Singularity, because all those things actually are 
separate processes.

-- 
Darren New / San Diego, CA, USA (PST)

Post a reply to this message

Warp wrote:

>   I faintly remember asking about this subject in the other group once.
> I think it was about how Haskell manages (or if it manages at all) to
> create precompiled (possibly dynamically-loadable) libraries which
> nevertheless work with any user-defined type and user-defined functions.

For statically-linked libraries, GHC needs both the object code and an 
"interface file" which tells it everything it could need to know about 
the stuff exported from the module (e.g., how many bytes of space does 
this exported type take up?) For dynamically-linked libraries, it's more 
tricky.

>   In object-oriented programming this is typically achieved with dynamic
> binding (ie. virtual functions): The precompiled library doesn't need
> to know the user-defined type as long as it has been inherited from a
> base class defined in the library. The virtual table attached to objects
> of that class allows the precompiled library to call the proper user-defined
> function. (In a way you could say that the user code is telling the library
> which function to call for each of the virtual functions in the base class.)
> 
>   However, how does haskell manage to do this? Suppose you have something
> like this precompiled into a dynamically loadable library:
> 
> foldl1 (+) someList
> 
>   Also assume the user has defined his own element type for the list and
> the (+) function for that element type, and then calls the dynamically
> loaded library by giving it a list with elements of that type. How does
> the library know which (+) function to call? How does it know that a (+)
> function exists for that element type in the first place?

The foldl1 function expects a list and a function that can operate on 
the elements of that list. In this case, all that happens is that the 
*caller* passes foldl1 a pointer to the appropriate implementation of 
(+) for the data type in question. The foldl1 function itself knows 
nothing about this; it's up to the caller. Since the caller presumably 
"knows about" this user-defined data type, that's no problem.

A more interesting example might be if somebody does

   sum someList

Now the library function "sum" is being passed a list. The type checker 
will ensure that the list can be summed, but how does the precompiled 
"sum" function know what the hell function to sum it with?

The answer is that under the covers, the compiled "sum" function 
actually takes an extra parameter pointing to a virtual table - exactly 
like in an OOP language. The caller has to provide a pointer to the 
correct table for the type in question.

And what if the caller doesn't know the type either? Well then the 
caller also takes a pointer as an extra hidden argument. And so on and 
so forth until we reach a point in the code where the type *is* 
statically known.

To summarise: if a type is statically known, the correct function is 
looked up at compile time. If a type is unknown at compile time, a 
virtual table pointer is secretly passed in.

(Actually, "sum" is a tiny little function, so it's rather likely to be 
inlined. If the function it's immediately inlined into knows the type 
statically, all the vtable lookups get optimised out. Alternatively, 
"sum" is still optimised to perform only 1 vtable lookup, not 1 on each 
iteration.)

Post a reply to this message

Orchid XP v8 wrote:

> I'll see if I can figure out what the current status of this feature 
> is... I'm curios myself.

Building libraries as DLLs used to work, but is currently broken.

You can still build a whole Haskell program as a DLL rather than an EXE, 
but that's all. (And why the hell would you want to? Load up 5 Haskell 
DLLs and you have 5 copies of the RTS and several copies of the Haskell 
libraries statically linked in... urgh!)

It was working until roughly GHC 6.4 (~2005), and then it broke. 
Apparently it's due to be back (on all platforms) in the next version of 
GHC - which is now actually overdue for release. (There was supposed to 
be an RC out by now.) The various developer docs are unclear as to 
whether this feature really will be present or not.

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> >   But doesn't that make each program selfish? In other words, it only takes
> > care of itself not running out of memory but completely disregards any other
> > program running in the system at the same time?

> Yes? And how is that different from, say, Windows or Linux? Maybe I'm 
> not understanding your point.

  When a C/C++ program frees at least a certain amount of memory in Windows
and Linux, that memory is also freed from the system, and becomes available
to other programs.

  If a GC'd program never runs the GC, it will keep all that memory reserved
even though it doesn't use it. Moreover, a GC'd system often allocates a
lot more memory than it really needs (because "freed" memory cannot be
reused until the GC is run).

-- 
                                                          - Warp

Post a reply to this message

Invisible <voi### [at] devnull> wrote:
> >   However, how does haskell manage to do this? Suppose you have something
> > like this precompiled into a dynamically loadable library:
> > 
> > foldl1 (+) someList
> > 
> >   Also assume the user has defined his own element type for the list and
> > the (+) function for that element type, and then calls the dynamically
> > loaded library by giving it a list with elements of that type. How does
> > the library know which (+) function to call? How does it know that a (+)
> > function exists for that element type in the first place?

> The foldl1 function expects a list and a function that can operate on 
> the elements of that list. In this case, all that happens is that the 
> *caller* passes foldl1 a pointer to the appropriate implementation of 
> (+) for the data type in question. The foldl1 function itself knows 
> nothing about this; it's up to the caller. Since the caller presumably 
> "knows about" this user-defined data type, that's no problem.

  You didn't understand me. The line "foldl1 (+) someList" is *in* the
precompiled library. It was not written by the user.

  When you are compiling the library you don't know what the type of
elements are in the list nor what is the correct (+) function to call
for those types.

> To summarise: if a type is statically known, the correct function is 
> looked up at compile time. If a type is unknown at compile time, a 
> virtual table pointer is secretly passed in.

  Exactly where is this virtual table pointer stored?

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:

>   You didn't understand me. The line "foldl1 (+) someList" is *in* the
> precompiled library. It was not written by the user.

Ah, I see.

Well "foldl1 (+)" is the implementation of "sum", which is indeed in the 
Haskell standard library (and hence precompiled). So what you're asking 
is, "what happens if I call 'sum' on some custom datatype that I just 
wrote?"

>   Exactly where is this virtual table pointer stored?

Each time you create a datatype that supports (+), (-), etc., the 
compiler generates a table pointing to the appropriate implementations 
of these functions for that datatype.

Each time you compile a function that accepts an arbitrary numeric type, 
the compiler secretly adds an extra pointer argument to that function. 
When a caller calls that function, the compiler secretly adds a pointer 
to the correct table into the function call. (And as I noted, if the 
caller doesn't know the type, it must have received a pointer itself in 
the same way, so it just passes that on.)

If that makes sense?

Post a reply to this message

Warp wrote:
>   When a C/C++ program frees at least a certain amount of memory in Windows
> and Linux, that memory is also freed from the system, and becomes available
> to other programs.

True. On the other hand, if you have a lot of small allocations and you 
can't condense them, you can wind up wasting a lot of memory because you 
have a few bytes allocated on each of dozens of pages. With a compacting 
GC, this situation doesn't occur.

>   If a GC'd program never runs the GC, it will keep all that memory reserved
> even though it doesn't use it. 

I imagine in this case you'd need to implement GC mechanisms that ran 
well. For example, you might force a GC after every N number of new 
pages are allocated.

Now you have me curious - I'll have to look at the code to see when the 
GC gets triggered. It'll be interesting to see how easy that is to find.

> Moreover, a GC'd system often allocates a
> lot more memory than it really needs (because "freed" memory cannot be
> reused until the GC is run).

On the other hand, a compacting GC doesn't have wasted space in the 
pages where the data is stored after a GC runs.

Certainly, a GCed program that doesn't run the GC often enough will 
waste memory, just like a Windows program that doesn't deallocate its 
memory resources when it's finished will use more memory than it needs 
to.  If your video game doesn't clean up the structures for dead aliens 
until you get to the end of the level, you're likely using up more 
memory than you need to.

Doctor, Doctor, it hurts when I do this.

-- 
Darren New / San Diego, CA, USA (PST)

Post a reply to this message