gdalgorithms-list

Re: [Algorithms] memory pool algorithms

[<Pau...@sc...>]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

> NOTE: address of an element is constant through its lifetime (between
> alloc and free), while index can change.
> 
> There are probably some errors by one above, but I hope the idea makes 
sense.
> :)

Thanks Alen, I *think* this is the same solution that Jeremiha posted and 
looks like it will suit my purposes nicely :)

Cheers, Paul.
**********************************************************************
This email and any files transmitted with it are confidential and intended 
solely for the use of the individual or entity to whom they are addressed. 
If you have received this email in error please notify pos...@sc...
This footnote also confirms that this email message has been checked for 
all known viruses.
Sony Computer Entertainment Europe Limited
Registered Office: 10 Great Marlborough Street, London W1F 7LP, United 
Kingdom
Registered in England: 3277793
**********************************************************************
P Please consider the environment before printing this e-mail

-----BEGIN PGP SIGNATURE-----
Version: PGP Universal 2.9.1 (Build 287)
Charset: US-ASCII

wsBVAwUBSfCXf3ajGqjtoMHxAQhieQf/VY6t9XBSm7Icwcqgqy/nQI+NXDvRRkYP
Trbgmv7+lbcIB5ZMbZHwnOcWJTTtujXCUIN8Lc5WN6ftvLLntkt3FZXKyMXfSiGQ
SxGjYjdVHa7EW9/5IbYC2ZvnmhQ9DoZncv/hq60WYAxJSwmQy1NVgxjSKwYehjRp
vEcZAWJUQADynEs/Up2MdoBnSPFfkl97lY2Bq0C1llqrHz0bGeo5B2Q71LUNJgBB
6Khq2pdEX+K7ORLVKTBJWud1rnmZXCqA9b9JaugK6EKQwym7GTMoah4XrKAEIsug
8uOz5dpl2O1FmsVpk61NBo6IInXnX08gTJSLOOzpNXd2lrChkCdNHA==
=U1Xi
-----END PGP SIGNATURE-----

Re: [Algorithms] memory pool algorithms

[Tom P. <ga...@fa...>]

> Have a allocated/free list that is an array of indices into the memory
> pool array.  The allocated/free list is divided such that the 0 through
> (M - 1) elements are allocated and the M through (N - 1) elements are
> free; just use an index to the start of the free elements.  The
> allocated/free list is initialized with 0 through (N - 1) and the start
> of the free list is index 0. When you allocate, increment the start of
> the free list index, when you free an element, decrement the index and
> swap the two elements.  To iterate over the allocated elements, iterate
> over the 0 through (M - 1) indices, and use the index to look up the
> object.  The problem with this is that you jump around memory when
> iterating.  If you are concerned with thrashing the cache, it would be
> better to just go through the array and skip empty elements.
> I was just wondering if anyone knew of an algorithm/method which
> facilitated simple memory pool allocation of a single type but with
> constant time allocation/deallocation/item retrieval by index and also
> provided a 'nice' way to iterate through the used elements?

That'll work ok, but you can skip the array of allocated/free element
indices if the objects are small enough and you don't need pointers into
them; just copy the "lastAllocated" element into the "newlyFreed" slot
when freeing, and always stick onto the end of the array.

An alternative, if your objects are "large" (so copying is undesirable) or
you need to keep pointers at particular elements, Alexandrescu's small
object allocator does most of this.

Allocate your pool of N elements.  reinterpret_cast the pointer to the
front of each element to an int and put my_index+1 into it.  (I.e. the
first 4 bytes of each element is the index of the next free element.  If
your object size is smaller than 4 bytes then adjust accordingly.)  Store
in the pool object a "first free", and init it to zero.

When you allocate an object, return the (constructed, if that's the way
you roll) first free element and set firstFree to what was in the first
four bytes of that element.

When you deallocate the object, destroy it as necessary, stick the value
of firstFree into the first four bytes and update firstFree to be
myAddress - baseAddress.

Now you can iterate through the free list in "random" order just by
following the indices.  You can't iterate the allocated list with this
setup, but you could certainly allocate a parallel bitfield that flagged
what was allocated and iterate that trivially.  I've done something to
this effect when I had to write a pooling allocator that allocated arrays
of these micro-objects.

The nice thing about this mechanism is that pointers to elements live for
the lifetime of the element as shuffling elements around means that
there's no (easy) way for people to hang onto one that they're interested
in.  On the other hand, if the objects are small and deallocation is rare
and nobody needs to know about one in particular (e.g. a particle system),
then clearly moving things around shouldn't be too terrible.  I believe
keeping a parallel bitfield would be more straight forward than an
unsorted array of free elements.

-tom!

Re: [Algorithms] memory pool algorithms

[Niklas F. <ni...@gr...>]

Pau...@sc... wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA256
> 
> Hi Guys,
> 
> I was just wondering if anyone knew of an algorithm/method which 
> facilitated simple memory pool allocation of a single type but with 
> constant time allocation/deallocation/item retrieval by index and also 
> provided a 'nice' way to iterate through the used elements?

Something like this perhaps. Constant time allocation, deallocation, 
retrieval and cache-friendly iteration with no holes. Code sketch in ruby:

(Note: Written for clarity rather than completely optimized. In an 
optimized version the freelist would be stored in-place in the @indices 
array, for instance.)

class IDArray
	def initialize
		@objects = []
		@ids = []
		@indices = []
		@freelist = []
	end

	def insert(o)
		i = @objects.size
		if @freelist.empty?
			id = @indices.size
		else
			id = @freelist.pop
		end
		@objects.push(o)
		@ids.push(id)
		@indices[id] = i
		return id
	end
		
	def lookup(id)
		return @objects[@indices[id]]
	end
		
	def remove(id)
		i = @indices[id]
		@objects[i] = @objects.last
		@ids[i] = @ids.last
		@objects.pop
		@ids.pop
		@indices[@ids[i]] = i
		@indices[id] = nil
		@freelist.push(id)
	end
		
	def each()
		@objects.each {|o| yield o}
	end
end

// Niklas

Re: [Algorithms] memory pool algorithms

[Mat N. <mat...@bu...>]

Or go here: http://www.bungie.net/images/Inside/publications/presentations/publicationsdes/engineering/butcher_gametech04.pdf

This is a presentation on Halo 2's architecture which has a few slides on how we handle what you are describing.

MSN
-----Original Message-----
From: Mat Noguchi
Sent: Thursday, April 23, 2009 9:33 AM
To: Game Development Algorithms
Subject: RE: [Algorithms] memory pool algorithms

Is the memory pool contiguous? If not, then it's kind of scary/impossible to have indexable access, but who knows? If it is contiguous, however, then you can use variants of a page table where the page size is the size of the type.

Also, you don't necessarily need a linked list for individual elements for iteration; you just need a way to know if a given slot is in use and the identifier used to access that slot. You can link those structures together if you allocate the storage for this pool in chunks (in the case of non-fixed pools).

Google "chris butcher index salt" without the quotes for some high level info as to how we do it.

MSN
-----Original Message-----
From: Pau...@sc... [mailto:Pau...@sc...]
Sent: Thursday, April 23, 2009 9:05 AM
To: Game Development Algorithms
Subject: Re: [Algorithms] memory pool algorithms

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

> I think this will work:
>
> Have a allocated/free list that is an array of indices into the memory
> pool array.  The allocated/free list is divided such that the 0 through
> (M - 1) elements are allocated and the M through (N - 1) elements are
> free; just use an index to the start of the free elements.  The
> allocated/free list is initialized with 0 through (N - 1) and the start
> of the free list is index 0. When you allocate, increment the start of
> the free list index, when you free an element, decrement the index and
> swap the two elements.  To iterate over the allocated elements, iterate
> over the 0 through (M - 1) indices, and use the index to look up the
> object.  The problem with this is that you jump around memory when
> iterating.  If you are concerned with thrashing the cache, it would be
> better to just go through the array and skip empty elements.

Thanks Jeremiah, thats excellent :) No linked lists, constant time
alloc/dealloc, element look up by index and its iterable (if there is such
a word). I guess the only thing is the order of elements as you iterate
through changes each time you dealloc, but thats unavoidable...

Cheers, Paul.
**********************************************************************
This email and any files transmitted with it are confidential and intended
solely for the use of the individual or entity to whom they are addressed.
If you have received this email in error please notify pos...@sc...
This footnote also confirms that this email message has been checked for
all known viruses.
Sony Computer Entertainment Europe Limited
Registered Office: 10 Great Marlborough Street, London W1F 7LP, United
Kingdom
Registered in England: 3277793
**********************************************************************
P Please consider the environment before printing this e-mail

-----BEGIN PGP SIGNATURE-----
Version: PGP Universal 2.9.1 (Build 287)
Charset: US-ASCII

wsBVAwUBSfCQk3ajGqjtoMHxAQjk/QgAqBwe74v42L2XJJQeDgSNQVEb2gpiiD4C
rr/0OOE4yMnUuSWfJXfjSDMq0Q9uoqProyJKrB7oLkc8CDrQ02Qc605a53uKab2p
IbJQthcxSOvcbn7SsEgH8nu/zEyD/0TbhZRLa4ZwBM/W50tm2Q6z0zhRpLLApx59
OJ39xtu1fkuzIoz1+fRnijNN1U7c6z/1re6x4eUZAKQLI9SavKqehmt0yzZqr7s7
o8kwtF2R/VzkWjaqilgbecBwbA4GO2ZjL417Qq3Obmr51l0G5WKLOfQZG7lfFAms
QV/DL0g+wJ9t7fogopnUQhSW6cSFpCACzQSpIx8T/cyKa8qMIh+BJQ==
=AxZj
-----END PGP SIGNATURE-----

------------------------------------------------------------------------------
Stay on top of everything new and different, both inside and
around Java (TM) technology - register by April 22, and save
$200 on the JavaOne (SM) conference, June 2-5, 2009, San Francisco.
300 plus technical and hands-on sessions. Register today.
Use priority code J9JMT32. http://p.sf.net/sfu/p
_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list

Re: [Algorithms] memory pool algorithms

[Mat N. <mat...@bu...>]

Is the memory pool contiguous? If not, then it's kind of scary/impossible to have indexable access, but who knows? If it is contiguous, however, then you can use variants of a page table where the page size is the size of the type.

Also, you don't necessarily need a linked list for individual elements for iteration; you just need a way to know if a given slot is in use and the identifier used to access that slot. You can link those structures together if you allocate the storage for this pool in chunks (in the case of non-fixed pools).

Google "chris butcher index salt" without the quotes for some high level info as to how we do it.

MSN
-----Original Message-----
From: Pau...@sc... [mailto:Pau...@sc...]
Sent: Thursday, April 23, 2009 9:05 AM
To: Game Development Algorithms
Subject: Re: [Algorithms] memory pool algorithms

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

> I think this will work:
>
> Have a allocated/free list that is an array of indices into the memory
> pool array.  The allocated/free list is divided such that the 0 through
> (M - 1) elements are allocated and the M through (N - 1) elements are
> free; just use an index to the start of the free elements.  The
> allocated/free list is initialized with 0 through (N - 1) and the start
> of the free list is index 0. When you allocate, increment the start of
> the free list index, when you free an element, decrement the index and
> swap the two elements.  To iterate over the allocated elements, iterate
> over the 0 through (M - 1) indices, and use the index to look up the
> object.  The problem with this is that you jump around memory when
> iterating.  If you are concerned with thrashing the cache, it would be
> better to just go through the array and skip empty elements.

Thanks Jeremiah, thats excellent :) No linked lists, constant time
alloc/dealloc, element look up by index and its iterable (if there is such
a word). I guess the only thing is the order of elements as you iterate
through changes each time you dealloc, but thats unavoidable...

Cheers, Paul.
**********************************************************************
This email and any files transmitted with it are confidential and intended
solely for the use of the individual or entity to whom they are addressed.
If you have received this email in error please notify pos...@sc...
This footnote also confirms that this email message has been checked for
all known viruses.
Sony Computer Entertainment Europe Limited
Registered Office: 10 Great Marlborough Street, London W1F 7LP, United
Kingdom
Registered in England: 3277793
**********************************************************************
P Please consider the environment before printing this e-mail

-----BEGIN PGP SIGNATURE-----
Version: PGP Universal 2.9.1 (Build 287)
Charset: US-ASCII

wsBVAwUBSfCQk3ajGqjtoMHxAQjk/QgAqBwe74v42L2XJJQeDgSNQVEb2gpiiD4C
rr/0OOE4yMnUuSWfJXfjSDMq0Q9uoqProyJKrB7oLkc8CDrQ02Qc605a53uKab2p
IbJQthcxSOvcbn7SsEgH8nu/zEyD/0TbhZRLa4ZwBM/W50tm2Q6z0zhRpLLApx59
OJ39xtu1fkuzIoz1+fRnijNN1U7c6z/1re6x4eUZAKQLI9SavKqehmt0yzZqr7s7
o8kwtF2R/VzkWjaqilgbecBwbA4GO2ZjL417Qq3Obmr51l0G5WKLOfQZG7lfFAms
QV/DL0g+wJ9t7fogopnUQhSW6cSFpCACzQSpIx8T/cyKa8qMIh+BJQ==
=AxZj
-----END PGP SIGNATURE-----

------------------------------------------------------------------------------
Stay on top of everything new and different, both inside and
around Java (TM) technology - register by April 22, and save
$200 on the JavaOne (SM) conference, June 2-5, 2009, San Francisco.
300 plus technical and hands-on sessions. Register today.
Use priority code J9JMT32. http://p.sf.net/sfu/p
_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list

Re: [Algorithms] memory pool algorithms

[<Pau...@sc...>]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

> I think this will work:
> 
> Have a allocated/free list that is an array of indices into the memory
> pool array.  The allocated/free list is divided such that the 0 through
> (M - 1) elements are allocated and the M through (N - 1) elements are
> free; just use an index to the start of the free elements.  The
> allocated/free list is initialized with 0 through (N - 1) and the start
> of the free list is index 0. When you allocate, increment the start of
> the free list index, when you free an element, decrement the index and
> swap the two elements.  To iterate over the allocated elements, iterate
> over the 0 through (M - 1) indices, and use the index to look up the
> object.  The problem with this is that you jump around memory when
> iterating.  If you are concerned with thrashing the cache, it would be
> better to just go through the array and skip empty elements.

Thanks Jeremiah, thats excellent :) No linked lists, constant time 
alloc/dealloc, element look up by index and its iterable (if there is such 
a word). I guess the only thing is the order of elements as you iterate 
through changes each time you dealloc, but thats unavoidable...

Cheers, Paul.
**********************************************************************
This email and any files transmitted with it are confidential and intended 
solely for the use of the individual or entity to whom they are addressed. 
If you have received this email in error please notify pos...@sc...
This footnote also confirms that this email message has been checked for 
all known viruses.
Sony Computer Entertainment Europe Limited
Registered Office: 10 Great Marlborough Street, London W1F 7LP, United 
Kingdom
Registered in England: 3277793
**********************************************************************
P Please consider the environment before printing this e-mail

-----BEGIN PGP SIGNATURE-----
Version: PGP Universal 2.9.1 (Build 287)
Charset: US-ASCII

wsBVAwUBSfCQk3ajGqjtoMHxAQjk/QgAqBwe74v42L2XJJQeDgSNQVEb2gpiiD4C
rr/0OOE4yMnUuSWfJXfjSDMq0Q9uoqProyJKrB7oLkc8CDrQ02Qc605a53uKab2p
IbJQthcxSOvcbn7SsEgH8nu/zEyD/0TbhZRLa4ZwBM/W50tm2Q6z0zhRpLLApx59
OJ39xtu1fkuzIoz1+fRnijNN1U7c6z/1re6x4eUZAKQLI9SavKqehmt0yzZqr7s7
o8kwtF2R/VzkWjaqilgbecBwbA4GO2ZjL417Qq3Obmr51l0G5WKLOfQZG7lfFAms
QV/DL0g+wJ9t7fogopnUQhSW6cSFpCACzQSpIx8T/cyKa8qMIh+BJQ==
=AxZj
-----END PGP SIGNATURE-----

Re: [Algorithms] memory pool algorithms

[Olivier G. <gal...@po...>]

On Thu, Apr 23, 2009 at 01:05:39PM +0100, Pau...@sc... wrote:
> I was just wondering if anyone knew of an algorithm/method which 
> facilitated simple memory pool allocation of a single type but with 
> constant time allocation/deallocation/item retrieval by index and also 
> provided a 'nice' way to iterate through the used elements?
> 
> We have a class which gives us everything but the last two together. We 
> can add a linked list of used elements (giving us the iteration) but then 
> you can't retrieve by index in constant time. Or we can retrieve by index 
> in constant time but then you can't iterate cleanly because there will be 
> holes in the memory pool.

Could you define "retrieve by index" further?  Do you mean that if "n"
elements are allocated they must be reachable by a number with 0 and
n-1?  If yes, you obviously can't have constant-time deletion, since
you'll have a mean of n/2 references to change for every deletion.
And if you allow holes to get constant-time deletion, what properties
do you want from your index that a pointer would not have?

  OG.

Re: [Algorithms] memory pool algorithms

[Alen L. <ale...@cr...>]

Depends on what you call a pool, but if you use a linear part of
memory for a pool, I believe you can use a two-way mapping between
addresses (with holes) and indices (without holes) to burn some extra
memory up front and gain O(1) in return: (warning, untested code!)

- n - max size
- P[n] - pool of preallocated elements
- I2A[n] - array of index to address mappings
- A2I[n] - array of address to index mappings
- F[n] - array of free addresses
- cf - count of free indices
- c - current allocated count

initialize:
  fill F with 0..n-1 (or reverse, if you prefer)
  cf = n
  c = 0

allocate:
  a = F[--cf]
  I2A[c] = a
  A2I[a] = c++
  return a

freebyaddress(a)
  F[cf++] = a
  i = A2I[a]
  I2A[i] = I2A[--c]

// iteration...
for(i=0;i<c;i++) {
  whatever(P[I2A[i]])
}

NOTE: address of an element is constant through its lifetime (between
alloc and free), while index can change.

There are probably some errors by one above, but I hope the idea makes sense.
:)

HTH,
Alen

Paul wrote at 4/23/2009:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA256

> Hi Guys,

> I was just wondering if anyone knew of an algorithm/method which 
> facilitated simple memory pool allocation of a single type but with 
> constant time allocation/deallocation/item retrieval by index and also
> provided a 'nice' way to iterate through the used elements?

> We have a class which gives us everything but the last two together. We
> can add a linked list of used elements (giving us the iteration) but then
> you can't retrieve by index in constant time. Or we can retrieve by index
> in constant time but then you can't iterate cleanly because there will be
> holes in the memory pool.

> Cheers, Paul.
> **********************************************************************
> This email and any files transmitted with it are confidential and intended
> solely for the use of the individual or entity to whom they are addressed.
> If you have received this email in error please notify pos...@sc...
> This footnote also confirms that this email message has been checked for
> all known viruses.
> Sony Computer Entertainment Europe Limited
> Registered Office: 10 Great Marlborough Street, London W1F 7LP, United
> Kingdom
> Registered in England: 3277793
> **********************************************************************
> P Please consider the environment before printing this e-mail

> -----BEGIN PGP SIGNATURE-----
> Version: PGP Universal 2.9.1 (Build 287)
> Charset: US-ASCII

> wsBVAwUBSfBYiXajGqjtoMHxAQjWewf+IQzmRj6+gox+qbzxG7tZ+AktKgCTDC+N
> 11Wgf8Pjo7szCdWTa3fk00T9mbNmNAtfuyFlo6tFUC310ggVETI7uItg1Enjy7/H
> 6unAfH1Nt14yUBI3bNZjOENXiB3ypP7EEY1wnFtSLeOTugNjUS8/xEyngv0JSiqV
> KXwg85XYpvJK5UoR4IrW3obyvaDJ+rWArRNAb167xCH80KlrrXFleVDLgPrjGRmJ
> vO202p2FNCNB6BsmuEK0LHWxG1n/A7sJKHlvPF32Ow5ADoMo2MxuzN7bos5hw3Yy
> CVrTKImbAP6Y3wf/vIE9HYUlZW9lwWctGOVziOLXQRAMSHkPwyNxbQ==
> =8a/D
> -----END PGP SIGNATURE-----

> ------------------------------------------------------------------------------
> Stay on top of everything new and different, both inside and 
> around Java (TM) technology - register by April 22, and save
> $200 on the JavaOne (SM) conference, June 2-5, 2009, San Francisco.
> 300 plus technical and hands-on sessions. Register today. 
> Use priority code J9JMT32. http://p.sf.net/sfu/p
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list



-- 
Alen

Re: [Algorithms] memory pool algorithms

[Jeremiah Z. <jer...@vo...>]

I think this will work:

Have a allocated/free list that is an array of indices into the memory
pool array.  The allocated/free list is divided such that the 0 through
(M - 1) elements are allocated and the M through (N - 1) elements are
free; just use an index to the start of the free elements.  The
allocated/free list is initialized with 0 through (N - 1) and the start
of the free list is index 0. When you allocate, increment the start of
the free list index, when you free an element, decrement the index and
swap the two elements.  To iterate over the allocated elements, iterate
over the 0 through (M - 1) indices, and use the index to look up the
object.  The problem with this is that you jump around memory when
iterating.  If you are concerned with thrashing the cache, it would be
better to just go through the array and skip empty elements.

-----Original Message-----
From: Pau...@sc... [mailto:Pau...@sc...] 
Sent: Thursday, April 23, 2009 7:06 AM
To: gda...@li...
Subject: [Algorithms] memory pool algorithms

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

Hi Guys,

I was just wondering if anyone knew of an algorithm/method which 
facilitated simple memory pool allocation of a single type but with 
constant time allocation/deallocation/item retrieval by index and also 
provided a 'nice' way to iterate through the used elements?

We have a class which gives us everything but the last two together. We 
can add a linked list of used elements (giving us the iteration) but
then 
you can't retrieve by index in constant time. Or we can retrieve by
index 
in constant time but then you can't iterate cleanly because there will
be 
holes in the memory pool.

Cheers, Paul.
**********************************************************************
This email and any files transmitted with it are confidential and
intended 
solely for the use of the individual or entity to whom they are
addressed. 
If you have received this email in error please notify
pos...@sc...
This footnote also confirms that this email message has been checked for

all known viruses.
Sony Computer Entertainment Europe Limited
Registered Office: 10 Great Marlborough Street, London W1F 7LP, United 
Kingdom
Registered in England: 3277793
**********************************************************************
P Please consider the environment before printing this e-mail

-----BEGIN PGP SIGNATURE-----
Version: PGP Universal 2.9.1 (Build 287)
Charset: US-ASCII

wsBVAwUBSfBYiXajGqjtoMHxAQjWewf+IQzmRj6+gox+qbzxG7tZ+AktKgCTDC+N
11Wgf8Pjo7szCdWTa3fk00T9mbNmNAtfuyFlo6tFUC310ggVETI7uItg1Enjy7/H
6unAfH1Nt14yUBI3bNZjOENXiB3ypP7EEY1wnFtSLeOTugNjUS8/xEyngv0JSiqV
KXwg85XYpvJK5UoR4IrW3obyvaDJ+rWArRNAb167xCH80KlrrXFleVDLgPrjGRmJ
vO202p2FNCNB6BsmuEK0LHWxG1n/A7sJKHlvPF32Ow5ADoMo2MxuzN7bos5hw3Yy
CVrTKImbAP6Y3wf/vIE9HYUlZW9lwWctGOVziOLXQRAMSHkPwyNxbQ==
=8a/D
-----END PGP SIGNATURE-----

------------------------------------------------------------------------
------
Stay on top of everything new and different, both inside and 
around Java (TM) technology - register by April 22, and save
$200 on the JavaOne (SM) conference, June 2-5, 2009, San Francisco.
300 plus technical and hands-on sessions. Register today. 
Use priority code J9JMT32. http://p.sf.net/sfu/p
_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-lis
t

Re: [Algorithms] memory pool algorithms

[Simon F. <sim...@po...>]

Pau...@sc... wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA256
> 
> Hi Guys,
> 
> I was just wondering if anyone knew of an algorithm/method which
> facilitated simple memory pool allocation of a single type but with
> constant time allocation/deallocation/item retrieval by index and
> also provided a 'nice' way to iterate through the used elements?   
> 
> We have a class which gives us everything but the last two together.
> We can add a linked list of used elements (giving us the iteration)
> but then you can't retrieve by index in constant time. Or we can
> retrieve by index in constant time but then you can't iterate cleanly
> because there will be holes in the memory pool.    
> 
> Cheers, Paul.

Are you after *something* like "An efficient Representation for Sparse
Sets"? (http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.30.7319)

AFFAIR it requires unique indices and I think the iteration might be in
"random" order, but maybe it can be tweaked.


Simon
-- 
___________________________________________________________________
Simon Fenney                              Principal Design Engineer
PowerVR Technologies     A Division of Imagination Technologies Ltd
Home Park Estate, Kings Langley, WD4 8LZ, UK     ph:+44 1923 260511
mailto:sim...@po...              http://www.powervr.com
___________________________________________________________________ 

"Your work is both good and original. Unfortunately the part that 
is good is not original and the part that is original is not good." 
- Samuel Johnson

"Plurality should not be assumed unnecessarily" - William of Occam,
Quodlibeta (c1324)

[Algorithms] memory pool algorithms

[<Pau...@sc...>]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

Hi Guys,

I was just wondering if anyone knew of an algorithm/method which 
facilitated simple memory pool allocation of a single type but with 
constant time allocation/deallocation/item retrieval by index and also 
provided a 'nice' way to iterate through the used elements?

We have a class which gives us everything but the last two together. We 
can add a linked list of used elements (giving us the iteration) but then 
you can't retrieve by index in constant time. Or we can retrieve by index 
in constant time but then you can't iterate cleanly because there will be 
holes in the memory pool.

Cheers, Paul.
**********************************************************************
This email and any files transmitted with it are confidential and intended 
solely for the use of the individual or entity to whom they are addressed. 
If you have received this email in error please notify pos...@sc...
This footnote also confirms that this email message has been checked for 
all known viruses.
Sony Computer Entertainment Europe Limited
Registered Office: 10 Great Marlborough Street, London W1F 7LP, United 
Kingdom
Registered in England: 3277793
**********************************************************************
P Please consider the environment before printing this e-mail

-----BEGIN PGP SIGNATURE-----
Version: PGP Universal 2.9.1 (Build 287)
Charset: US-ASCII

wsBVAwUBSfBYiXajGqjtoMHxAQjWewf+IQzmRj6+gox+qbzxG7tZ+AktKgCTDC+N
11Wgf8Pjo7szCdWTa3fk00T9mbNmNAtfuyFlo6tFUC310ggVETI7uItg1Enjy7/H
6unAfH1Nt14yUBI3bNZjOENXiB3ypP7EEY1wnFtSLeOTugNjUS8/xEyngv0JSiqV
KXwg85XYpvJK5UoR4IrW3obyvaDJ+rWArRNAb167xCH80KlrrXFleVDLgPrjGRmJ
vO202p2FNCNB6BsmuEK0LHWxG1n/A7sJKHlvPF32Ow5ADoMo2MxuzN7bos5hw3Yy
CVrTKImbAP6Y3wf/vIE9HYUlZW9lwWctGOVziOLXQRAMSHkPwyNxbQ==
=8a/D
-----END PGP SIGNATURE-----

Re: [Algorithms] Complexity of new hardware

[Andrew V. <and...@ni...>]

Actually, I think that's a perfectly fine feature if all you care about is
one or two fixed platforms that you already compile for separately anyway.
Which is quite a few us. :)

Knowing exactly how many cores you have and figuring that info in at compile
time might also enable better optimisation or layout of the code by the
compiler as well.

Cheers,
Andrew. 

> -----Original Message-----
> From: Gregory Junker [mailto:gj...@da...] 
> Sent: 22 April 2009 18:32
> To: 'Game Development Algorithms'; and...@ni...
> Subject: Re: [Algorithms] Complexity of new hardware
> 
> > parallel evaluation. For example, GHC (arguably the most mature 
> > Haskell
> > compiler) can compile for an arbitrary number of cores
> 
> I don't think that's a desirable feature -- limiting your 
> scalability at compile time, that is.
> 
> Greg
> 
> 
> --------------------------------------------------------------
> ----------------
> Stay on top of everything new and different, both inside and 
> around Java (TM) technology - register by April 22, and save 
> $200 on the JavaOne (SM) conference, June 2-5, 2009, San Francisco.
> 300 plus technical and hands-on sessions. Register today. 
> Use priority code J9JMT32. http://p.sf.net/sfu/p 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgo
rithms-list
> 
> ______________________________________________________________________
> This email has been scanned by the MessageLabs Email Security System.
> For more information please visit 
> http://www.messagelabs.com/email 
> ______________________________________________________________________
> 

Re: [Algorithms] Complexity of new hardware

[Sam M. <sam...@ge...>]

Apologies - I'm still pretty new to Haskell and messed up my facts here.


You specify the number of cores at runtime rather than compile time.
>From the ghc user guide:
http://haskell.org/ghc/docs/latest/html/users_guide/using-smp.html

ta,
Sam

-----Original Message-----
From: Gregory Junker [mailto:gj...@da...] 
Sent: 22 April 2009 18:32
To: 'Game Development Algorithms'; and...@ni...
Subject: Re: [Algorithms] Complexity of new hardware

> parallel evaluation. For example, GHC (arguably the most mature
Haskell
> compiler) can compile for an arbitrary number of cores

I don't think that's a desirable feature -- limiting your scalability at
compile time, that is.

Greg


------------------------------------------------------------------------
------
Stay on top of everything new and different, both inside and 
around Java (TM) technology - register by April 22, and save
$200 on the JavaOne (SM) conference, June 2-5, 2009, San Francisco.
300 plus technical and hands-on sessions. Register today. 
Use priority code J9JMT32. http://p.sf.net/sfu/p
_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-lis
t

Re: [Algorithms] Complexity of new hardware

[Gregory J. <gj...@da...>]

> parallel evaluation. For example, GHC (arguably the most mature Haskell
> compiler) can compile for an arbitrary number of cores

I don't think that's a desirable feature -- limiting your scalability at
compile time, that is.

Greg

Re: [Algorithms] Complexity of new hardware

[Sam M. <sam...@ge...>]

> Wouldn't that be a tough sell? You'd already be competing with free 
> implementations of LUA, Python, JavaScript and their ilk on the low
end, 
> and built-in languages like UnrealScript on the high end. 

I don't think there's a market for that kind of scripting DSL. A new
language would need to eat into the remaining C++ development burden
that isn't suitable to implementing in Lua, say. Which is plenty.

> Doesn't this bring us back full circle? I recall a statement from a 
> month ago saying that we all need to think differently about how we
put 
> together massively parallel software, because the current tools don't 
> really help us in the right ways... 

Another reason to consider pure functional languages. This is a much
deeper topic that I'm now about to trivialise, but the referential
transparency of these languages makes them particular suitable to
parallel evaluation. For example, GHC (arguably the most mature Haskell
compiler) can compile for an arbitrary number of cores, although it's
still an active research area as I understand it.

Thanks,
Sam

------------------------------------------------------------------------
------
Stay on top of everything new and different, both inside and 
around Java (TM) technology - register by April 22, and save
$200 on the JavaOne (SM) conference, June 2-5, 2009, San Francisco.
300 plus technical and hands-on sessions. Register today. 
Use priority code J9JMT32. http://p.sf.net/sfu/p
_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-lis
t

Re: [Algorithms] Complexity of new hardware

[Marc B. R. <mar...@or...>]

How the backend is handled is irrelevant to what I was attempting to say,
which is basically I don't believe in any "fits-all" languages.


-----Original Message-----
From: Sam Martin [mailto:sam...@ge...] 
Sent: Wednesday, April 22, 2009 5:59 PM
To: Alen Ladavac; Game Development Algorithms; Gregory Junker
Subject: Re: [Algorithms] Complexity of new hardware


Exactly - C/C++ is an excellent target format.

Haskell already compiles 'via-c'. I'd be looking at targeting any domain
specific language at generating C/C++, not assembly. This would also greatly
ease interoperability with other C/C++ which (as previously discussed on
this list) is absolutely essential.

I note that generating C/C++ doesn't mean you can't run your DSL in an
interpreted mode for fast development/debugging. I'd expect the tight
control over side effects in functional languages to aid this.

Ta,
Sam

-----Original Message-----
From: Alen Ladavac [mailto:ale...@cr...] 
Sent: 22 April 2009 16:35
To: Gregory Junker
Cc: 'Game Development Algorithms'
Subject: Re: [Algorithms] Complexity of new hardware

Just that the safest bet for the common representation is C++. It already
compiles to high-performance code on all platforms. :p

Alen

Gregory wrote at 4/22/2009:


CLR, in other words.  ;)
 

From: Marc B. Reynolds [mailto:mar...@or...] 
Sent: Wednesday, April 22, 2009 4:56 AM
To: 'Game Development Algorithms'
Subject: Re: [Algorithms] Complexity of new hardware
 
IMHO the best solution is multiple HL languages that frontend compile into a
common high-level IR. 
 
I like functional languages, but most worldbuilders/scripters should
(virtually) never need to write in one. 





-- 
Alen


------------------------------------------------------------------------
------
Stay on top of everything new and different, both inside and 
around Java (TM) technology - register by April 22, and save $200 on the
JavaOne (SM) conference, June 2-5, 2009, San Francisco. 300 plus technical
and hands-on sessions. Register today. 
Use priority code J9JMT32. http://p.sf.net/sfu/p
_______________________________________________
GDAlgorithms-list mailing list GDA...@li...
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-lis
t

----------------------------------------------------------------------------
--
Stay on top of everything new and different, both inside and 
around Java (TM) technology - register by April 22, and save $200 on the
JavaOne (SM) conference, June 2-5, 2009, San Francisco. 300 plus technical
and hands-on sessions. Register today. 
Use priority code J9JMT32. http://p.sf.net/sfu/p
_______________________________________________
GDAlgorithms-list mailing list GDA...@li...
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list

Re: [Algorithms] Complexity of new hardware

[Andrew V. <and...@ni...>]

> Wouldn't that be a tough sell? You'd already be competing 
> with free implementations of LUA, Python, JavaScript and 
> their ilk on the low end, and built-in languages like 
> UnrealScript on the high end. While middleware for something 
> like mesh exporting and animation (Granny) or something like 
> networking or AI make sense, because there is no good free 
> library for those areas, the scripting language market seems 
> full of entrenched competitors with a zero dollar price point.

Maybe "scripting language" is the wrong term. I'm thinking of something that
sits between the low-level C/C++ "details" and the high-level, LUA-style,
scripting - probably for the purpose of enabling easier multithreading of
gameplay style code (rather than engine-side code).

I'm not saying you can't extend this language in either direction, but
that's where I see the most use of it (YMMV). :)

> > There definitely needs to be a change to the way most games are 
> > written when considering new hardware. It's perfectly 
> possible that a 
> > new/different language might be a good way to go - however, I'd be 
> > concerned that it would introduce more complexity, i.e.
> 
> Doesn't this bring us back full circle? I recall a statement 
> from a month ago saying that we all need to think differently 
> about how we put together massively parallel software, 
> because the current tools don't really help us in the right 
> ways... That's not just games, mind you, but business 
> software is often less performance critical, and server 
> software already has a reasonable parallelization strategy 
> with data and service federation (and 800-way CPU boxes like 
> those from Azul...).

Yep, agreed.
My point was more whether the best way forward would be with a new language
or whether new/different programming techniques for existing languages
(which means C++, I guess) would be better.

Cheers,
Andrew.

Re: [Algorithms] Complexity of new hardware

[Jon W. <jw...@gm...>]

Andrew Vidler wrote:
> Yes, I think there is.
> But I think you'd be competing with (possibly lower-level) scripting 
> languages rather than engine level C/C++. Not that that's necessarily 
> a bad thing.

Wouldn't that be a tough sell? You'd already be competing with free 
implementations of LUA, Python, JavaScript and their ilk on the low end, 
and built-in languages like UnrealScript on the high end. While 
middleware for something like mesh exporting and animation (Granny) or 
something like networking or AI make sense, because there is no good 
free library for those areas, the scripting language market seems full 
of entrenched competitors with a zero dollar price point.

>
> There definitely needs to be a change to the way most games are 
> written when considering new hardware. It's perfectly possible that a 
> new/different language might be a good way to go - however, I'd be 
> concerned that it would introduce more complexity, i.e.

Doesn't this bring us back full circle? I recall a statement from a 
month ago saying that we all need to think differently about how we put 
together massively parallel software, because the current tools don't 
really help us in the right ways... That's not just games, mind you, but 
business software is often less performance critical, and server 
software already has a reasonable parallelization strategy with data and 
service federation (and 800-way CPU boxes like those from Azul...).

Sincerely,

jw

Re: [Algorithms] Complexity of new hardware

[Sam M. <sam...@ge...>]

Exactly - C/C++ is an excellent target format.

Haskell already compiles 'via-c'. I'd be looking at targeting any domain
specific language at generating C/C++, not assembly. This would also
greatly ease interoperability with other C/C++ which (as previously
discussed on this list) is absolutely essential.

I note that generating C/C++ doesn't mean you can't run your DSL in an
interpreted mode for fast development/debugging. I'd expect the tight
control over side effects in functional languages to aid this.

Ta,
Sam

-----Original Message-----
From: Alen Ladavac [mailto:ale...@cr...] 
Sent: 22 April 2009 16:35
To: Gregory Junker
Cc: 'Game Development Algorithms'
Subject: Re: [Algorithms] Complexity of new hardware

Just that the safest bet for the common representation is C++. It
already compiles to high-performance code on all platforms. :p

Alen

Gregory wrote at 4/22/2009:


CLR, in other words.  ;)
 

From: Marc B. Reynolds [mailto:mar...@or...] 
Sent: Wednesday, April 22, 2009 4:56 AM
To: 'Game Development Algorithms'
Subject: Re: [Algorithms] Complexity of new hardware
 
IMHO the best solution is multiple HL languages that frontend compile
into a common high-level IR. 
 
I like functional languages, but most worldbuilders/scripters should
(virtually) never need to write in one. 





-- 
Alen


------------------------------------------------------------------------
------
Stay on top of everything new and different, both inside and 
around Java (TM) technology - register by April 22, and save
$200 on the JavaOne (SM) conference, June 2-5, 2009, San Francisco.
300 plus technical and hands-on sessions. Register today. 
Use priority code J9JMT32. http://p.sf.net/sfu/p
_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-lis
t

Re: [Algorithms] Complexity of new hardware

[Alen L. <ale...@cr...>]

Just that the safest bet for the common representation is C++. It already compiles to high-performance code on all platforms. :p

Alen

Gregory wrote at 4/22/2009:


CLR, in other words.  ;)
 

From: Marc B. Reynolds [mailto:mar...@or...] 
Sent: Wednesday, April 22, 2009 4:56 AM
To: 'Game Development Algorithms'
Subject: Re: [Algorithms] Complexity of new hardware
 
IMHO the best solution is multiple HL languages that frontend compile into a common high-level IR. 
 
I like functional languages, but most worldbuilders/scripters should (virtually) never need to write in one. 





-- 
Alen

Re: [Algorithms] Complexity of new hardware

[Marc B. R. <mar...@or...>]

 > CLR, in other words.  ;) 
 
I said a high level IR, not FORTH! 

Re: [Algorithms] Complexity of new hardware

[Gregory J. <gj...@da...>]

CLR, in other words.  ;)

 

  _____  

From: Marc B. Reynolds [mailto:mar...@or...] 
Sent: Wednesday, April 22, 2009 4:56 AM
To: 'Game Development Algorithms'
Subject: Re: [Algorithms] Complexity of new hardware

 

IMHO the best solution is multiple HL languages that frontend compile into a
common high-level IR. 

 

I like functional languages, but most worldbuilders/scripters should
(virtually) never need to write in one. 

Re: [Algorithms] Complexity of new hardware

[Marc B. R. <mar...@or...>]

IMHO the best solution is multiple HL languages that frontend compile into a
common high-level IR. 
 
I like functional languages, but most worldbuilders/scripters should
(virtually) never need to write in one. 

Re: [Algorithms] Complexity of new hardware

[Andrew V. <and...@ni...>]

Yes, I think there is.
But I think you'd be competing with (possibly lower-level) scripting
languages rather than engine level C/C++. Not that that's necessarily a bad
thing.
Of course, if you could get a language that interfaced correctly and
completely with all the existing SDKs on all platforms and you could use it
to write/generate code that ran in comparable time to equivalent C then it
could be a valid replacement for everything. But I reckon a script-style
language is a more feasible goal to start with.
 
There definitely needs to be a change to the way most games are written when
considering new hardware. It's perfectly possible that a new/different
language might be a good way to go - however, I'd be concerned that it would
introduce more complexity, i.e. if you already expect people to change the
way they program, is it too much to expect them to do so while also learning
a completely new language?
Maybe not - maybe the language can help the process?
 
Cheers,
Andrew.


  _____  

From: Sam Martin [mailto:sam...@ge...] 
Sent: 22 April 2009 11:05
To: Game Development Algorithms
Subject: Re: [Algorithms] Complexity of new hardware



Here’s a fairly crazy idea, but I’d like to put it out there anyway: Is
there a middleware market for something like GOAL?

 

Frankly, I have no idea whether it could make money - I’m not interested in
worrying about this at the moment (and it’s off topic). But I am interested
in finding out whether the industry would actually be interesting in
adopting one or more domain-specific languages in games development?

 

As an example, I’ve been particularly impressed by Haskell. It’s a pure,
strictly-typed “lazy” functional language and looks like a good fit in many
ways. I won’t rattle on about how cool it is here, but suffice to say I
think it warrants some attention. The slightly iffy state of its C
compatibility currently lets it down (IMHO), but I think some sort of
“Haskell for games dev” project/compiler/code generator is a not totally
insane idea.

 

Any thoughts?

 

Cheers,

Sam

 

From: Pal-Kristian Engstad [mailto:pal...@na...] 
Sent: 21 April 2009 20:44
To: Game Development Algorithms
Subject: Re: [Algorithms] Complexity of new hardware

 

Gregory Junker wrote: 

NaughtyDog tried -- you have to admit that Lisp *in theory* should be



perfectly suited to game development: it's core design intent is list
processing (indeed, it's the name), which arguably games *are*, and it's
functional, which ought to be perfect for increasingly data-parallel game
technology designs. If the syntax is just "too weird" -- that can be
changed, while leaving the core language design intact (again, GOAL). 
 
http://www.gamasutra.com/features/20020710/white_02.htm
  

I'll have to correct you in some of your assumptions. Goal:

*	Was imperative and not (very) functional. For instance, it didn't
support closures. 

*	Had okey (but not great) object-oriented support. 

*	Had good introspection qualities (except where you didn't need to
have it). 

*	Had an excellent macro processor, corresponding to Lisp. 

*	Had excellent support for fibers. 

*	Made use of the REPL style of programming, including on-line updates
of code and data. 

*	Was an excellent assembler, since you had register scope as well as
access to macros and direct access to "high-level" data types. 

*	Was quite a poor code generator (but it didn't matter because of the
above). 

*	Had no visual debugger, but the REPL and on-line updates usually
negated the need for one. 

Goal was a great system - one that we still greatly miss. If we had to make
a Goal2, then we'd probably:

*	Use an SML-ish or Scala-ish surface syntax, while trying to retain
the power of Lisp macros. 

*	Introduce stronger typing features, which is difficult, given the
need for REPL and hot updates. 

*	Do more in terms of high-level optimization, though LLVM might
negate the need for some of that. 

*	Go towards a more functional style, especially due to current
generation hardware's need for concurrency. 

Before anyone jumps up and down, no - we're probably never going to get
around doing this. We simply don't have the time to spend too much effort on
such an en devour. 

Thanks,

PKE.



-- 
Pål-Kristian Engstad (en...@na...), 
Lead Graphics & Engine Programmer,
Naughty Dog, Inc., 1601 Cloverfield Blvd, 6000 North,
Santa Monica, CA 90404, USA. Ph.: (310) 633-9112.
 
"Emacs would be a far better OS if it was shipped with 
 a halfway-decent text editor." -- Slashdot, Dec 13. 2005.
 

______________________________________________________________________
This email has been scanned by the MessageLabs Email Security System.
For more information please visit http://www.messagelabs.com/email 
______________________________________________________________________

Re: [Algorithms] Complexity of new hardware

[Sam M. <sam...@ge...>]

Here's a fairly crazy idea, but I'd like to put it out there anyway: Is there a middleware market for something like GOAL?

 

Frankly, I have no idea whether it could make money - I'm not interested in worrying about this at the moment (and it's off topic). But I am interested in finding out whether the industry would actually be interesting in adopting one or more domain-specific languages in games development?

 

As an example, I've been particularly impressed by Haskell. It's a pure, strictly-typed "lazy" functional language and looks like a good fit in many ways. I won't rattle on about how cool it is here, but suffice to say I think it warrants some attention. The slightly iffy state of its C compatibility currently lets it down (IMHO), but I think some sort of "Haskell for games dev" project/compiler/code generator is a not totally insane idea.

 

Any thoughts?

 

Cheers,

Sam

 

From: Pal-Kristian Engstad [mailto:pal...@na...] 
Sent: 21 April 2009 20:44
To: Game Development Algorithms
Subject: Re: [Algorithms] Complexity of new hardware

 

Gregory Junker wrote: 

NaughtyDog tried -- you have to admit that Lisp *in theory* should be



perfectly suited to game development: it's core design intent is list
processing (indeed, it's the name), which arguably games *are*, and it's
functional, which ought to be perfect for increasingly data-parallel game
technology designs. If the syntax is just "too weird" -- that can be
changed, while leaving the core language design intact (again, GOAL). 
 
http://www.gamasutra.com/features/20020710/white_02.htm
  

I'll have to correct you in some of your assumptions. Goal:

*	Was imperative and not (very) functional. For instance, it didn't support closures.
*	Had okey (but not great) object-oriented support.
*	Had good introspection qualities (except where you didn't need to have it).
*	Had an excellent macro processor, corresponding to Lisp.
*	Had excellent support for fibers.
*	Made use of the REPL style of programming, including on-line updates of code and data.
*	Was an excellent assembler, since you had register scope as well as access to macros and direct access to "high-level" data types.
*	Was quite a poor code generator (but it didn't matter because of the above).
*	Had no visual debugger, but the REPL and on-line updates usually negated the need for one.

Goal was a great system - one that we still greatly miss. If we had to make a Goal2, then we'd probably:

*	Use an SML-ish or Scala-ish surface syntax, while trying to retain the power of Lisp macros.
*	Introduce stronger typing features, which is difficult, given the need for REPL and hot updates.
*	Do more in terms of high-level optimization, though LLVM might negate the need for some of that.
*	Go towards a more functional style, especially due to current generation hardware's need for concurrency.

Before anyone jumps up and down, no - we're probably never going to get around doing this. We simply don't have the time to spend too much effort on such an en devour. 

Thanks,

PKE.



-- 
Pål-Kristian Engstad (en...@na...), 
Lead Graphics & Engine Programmer,
Naughty Dog, Inc., 1601 Cloverfield Blvd, 6000 North,
Santa Monica, CA 90404, USA. Ph.: (310) 633-9112.
 
"Emacs would be a far better OS if it was shipped with 
 a halfway-decent text editor." -- Slashdot, Dec 13. 2005.