LOOM and Virtual Memory

Mariano,

many of the lessons learned from LOOM still apply, in my opinion. Just
imagine that you need an image larger than 4GB on a 32 bit machine
(there are still many of those around).

I don't think pointer sizes
are as much of a problem for directly adopting LOOM today as the
widespread use of direct pointers instead of object tables.

But it
would be certainly possible to adapt things using the "pointer
swizzling" from the Texas guys:

http://portal.acm.org/citation.cfm?id=1267991.1267999

Though LOOM was created to fix several problems of the previous
design, OOZE, that was a system that was actually used in production
for several years and you might find some interesting ideas there:

http://www-cs-students.stanford.edu/~eswierk/misc/kaehler81/

A very advanced virtual memory system for Smalltalk was the one
developed for the Mushroom project in the early 1990s. Several papers
describe different aspects of it at:

http://www.wolczko.com/mushroom/index.html

Hi Mariano:

I was not able to find a copy of that paper. The ACM link offers only
the bibliographic data.

Do you have an alternative link, or could you provide us at least with
the abstract?

How does your interest relate to for instance NXTalk?
http://www.hpi.uni-potsdam.de/hirschfeld/projects/nxtalk/index.html

If I remember correctly, these Lego devices are also using two
different kinds of memory, a fast and small RAM and some flash memory.
But I don't remember well, who that was solved in NXTalk.

Best regards
Stefan

On Feb 9, 4:16 pm, Mariano Martinez Peck <[hidden email]>
wrote:

> Hi and welcome!!  Now that there are people registered, we can start to
> discuss :)
>
> During the last two weeks or so I have been reading and understanding (into
> the very deep details) the LOOM (Large Object Oriented Memory) paper that
> you can find here:http://portal.acm.org/citation.cfm?id=94112
>
> LOOM was a Virtual Memory scheme for Smalltalk-80. I really like that paper
> and I want to know if there is some newer implementation. Why newer?
>
> - Most of the problems/solution it presents, were because of the limited GC
> techniques used by that time. Nowadays GCs take into account most of those
> problems, thus a lot of complexity should be reduced
> - The key point of LOOM is that it uses 16 bits addresses for primary memory
> (RAM) and 32 bits addresses for secondary memory (disk). Most of the
> problems and complexity of LOOM are due to this. I think we don't have this
> problem nowadays.
>
> So, I think that a LOOM implementation nowadays, with same pointer sizes and
> modern GC, should be much simpler.
>
> Are you aware of newer implementation ?
>
> I am interested in Virtual Memory scheme in general, not necessary LOOM.
> Something that stands the following two phrases (extracted form LOOM paper):
>
> “Primary memory is a cache for objects temporarily involved in computation."
> "Objects live permanently in secondary memory and cycle into primary as they
> are needed in computation."
>
> Thanks for any comments you can give me.
>
> Cheers
>
> Mariano

On Feb 9, 9:07 pm, Mariano Martinez Peck <[hidden email]>
wrote:

> http://portal.acm.org/citation.cfm?id=28707

Thanks.

> However, my idea is not to
> have a complete different VM neither image. It would be cool to have a
> "standard" VM that can have a mechanism to act as Virtual Memory. This can
> be VERY valuated in such devices, but probably also useful for a desktop
> application. Suppose you are deploying a seaside app. The image takes 50 mb.
> Why ?  ok, that's not too much....but if you have several images
> running...that can be a lot. And what percentage of the image is really used
> ?  why I should use 50 if maybe I just use 10 ?

Hm, am not entirely sure, but thats sounds much more like you are
looking for a garbage collector which is aware of paging/virtual
memory provided by the operating system.

Even so, I think that VMs
should take more responsibilities and OS should be more like an
extended hypervisor, wouldn't it be a practical solution to have
something like a generational GC which might also take the history of
reads/writes into account when it moves objects in memory?

I would
guess, that such a GC would allow the OS to swap out unused stuff to
the disk easily.

From the top of my head, I don't remember any GC which did such a
thing, but the lecture I followed on the IBM Metronome GC gave me the
impression, that they do very similar stuff, to what I vaguely
remember from my OS lectures (http://www.cs.uoregon.edu/research/
summerschool/summer09/curriculum.html see David Bacon).

> I know you are developing VMs also (or similar). I have your rss and I
> saw your paper the other day....it is in my toreads

Well, kind of related to your question, too: http://doi.acm.org/10.1145/1640134.1640149
Here, David has divided the heap in a read/write and read-mostly heap.

For our usecase that works well, for your I think you need a more
sophisticated solution. And, well, I have ported that VM to standard
multi-core hardware, nothing more to report on for the moment :-/

Mariano,

Gemstone was something that I considered mentioning, but since I don't
have a good reference for it handy, I didn't. It is certainly worth
looking into.

Mariano,

Gemstone was something that I considered mentioning, but since I don't
have a good reference for it handy, I didn't. It is certainly worth
looking into.

Virtual memory will only help with the problem of limited RAM if you
have a device to swap to, either locally on over a fast network. That
would be the case for a PDA if it had something like 8MB of RAM and
64MB of Flash but you couldn't directly address the Flash for some
reason. It certainly isn't true of something like the NXT and many
other embedded devices.

When using virtual memory to deal with limited RAM, having an
intermediate level using compressed data in RAM normally helps.

Craig Latta's work on Spoon might be interesting for you, though there
is little documentation about it, unfortunately.

http://netjam.org/projects/spoon/

His patches to the Squeak VM are very small. The idea is that two or
more images can talk to each other and move objects between them. So
you can have something like a virtual memory where the "swap device"
is actually another, much larger and fully running Squeak image
instead of a simple file.

I have done a lot of work on really small implementations, but those
involved hardware, virtual machine and image format changes. Just
going from 32 bits to 16 saves about 33% of the RAM.

I used OOZE style
pointer encoding to eliminate the object headers. I don't think any of
that stuff would help with your goals.

About the LOOM paper, the system is also described in chapter 14
(pages 251 to 271) of "Smalltalk-80: Bits of History, Words of
Advice" (the "green book") which is available online at

http://stephane.ducasse.free.fr/FreeBooks/BitsOfHistory/

Mariano,

> > When using virtual memory to deal with limited RAM, having an
> > intermediate level using compressed data in RAM normally helps.
>
> compressing which kind of data ? internal representation of the object model
> ?

In the case of a paged virtual memory system, it would be the pages
that would be compressed. This works well if the processor is fast
compared to the speeds of the network or the local swap device. The
main RAM is divided into two regions: normal data and a cache for
compressed pages. When a page is supposed to be sent back to the
backing store, it is instead compressed and saved in the cache. If it
is not used for a while then it actually goes to the swap file, but if
it is requested again before that then it can simply be uncompressed.
The sizes of the two regions have to be carefully chosen or this
scheme can perform worse than a simple virtual memory. If done right,
however, it can perform the same as a machine with twice as much
physical RAM.

For the design I am working on for Squeak,

the "swap file" is actually
a large number of smaller files stored in a compressed format.

If any
object in one of these is needed, the whole file is brought into a
special "compressed segments" region of RAM and the individual objects
are expanded as needed.

In LOOM terms, this is like converting a whole
group of objects from "not resident" to leafs.

Unlike pages, objects
have different sizes so changing their contents and compressing will
probably result in something that won't fit where the original
compressed object was. No problem - I just save it elsewhere like all
good journalling systems should.

> > [work on tiny images - 16 bits]

>
> This work you did was "recently" or several years ago ?  I ask because I
> wonder how you manage to work with 16 bits pointers while the world of the
> OS and processor is 32 or even 64.

This was done in 2001 and was a real product rather than a research
project. The machine had only 512KB of Flash but a full 8MB of RAM, so
some of my constraint were the opposite of what we normally had. I
used a full class/method table for lookups, for example.

That is
extremely wasteful (normally more than 80% of the entries will point
to "Does Not Understand") but it gave me a guaranteed 1 clock cycle
message send. Even with compression, I wouldn't get more than 32K
objects in 512KB so 16 bit pointers were a nice fit. The processor was
one that I designed myself, so if other people are doing 32 and 64
bits it didn't matter to me.

http://www.merlintec.com:8080/hardware/Oliver