Should Resizable*Array's be chunked lists?

Bernhard Schmalhofer

unread,

Oct 20, 2004, 5:17:34 PM10/20/04

to perl6-i...@perl.org

Hi,

I have started to work on some of the missing ops for the Resizable*Array
PMCs.
I noticed that, unlike the Array and PerlArray PMC, they currently do not
use the functionality from src/list.c.
This means that a ResizablePMCArray cannot be broken up in chunks and

set P0, .ResizablePMCArray
P0[1000] = 1000

causes a lot of memory allocation.

Is there a design reason for not having a chunked implementation?

I have started to cut&paste some code from array.pmc to
resizablepmcarray.pmc.
So far it looks OK, with only test 15 of t/op/gc.t and test 10 of
t/pmc/resizablepmcarray.t failing.

One thing, that is propably hard to cover, is the method "sort" inherited
from FixedPMCArray. It looks like 'qsort' needs a continous piece of memory
for sorting.

CU, Bernhard

--
/* Bernhard.S...@biomax.de */

GMX ProMail mit bestem Virenschutz http://www.gmx.net/de/go/mail
+++ Empfehlung der Redaktion +++ Internet Professionell 10/04 +++

Leopold Toetsch

unread,

Oct 21, 2004, 5:52:50 AM10/21/04

to Bernhard Schmalhofer, perl6-i...@perl.org

Bernhard Schmalhofer <Bernhard.S...@gmx.de> wrote:
> Hi,

> Is there a design reason for not having a chunked implementation?

Then you could use Array/PerlArray anyway (modulo the PerlUndef).

> One thing, that is propably hard to cover, is the method "sort" inherited
> from FixedPMCArray. It looks like 'qsort' needs a continous piece of memory
> for sorting.

Well, qsort can't remain for various reasons. The main one is that it
doesn't allow additional params to be passed to the sort function.
Currently these are static globals, which makes the sort non-reentrant.

For performance reasons we might need some sort/merge algorithm anyway
and then it can work through chunks too.

> CU, Bernhard

leo

Dan Sugalski

unread,

Oct 21, 2004, 9:32:02 AM10/21/04

to Bernhard Schmalhofer, perl6-i...@perl.org

At 11:17 PM +0200 10/20/04, Bernhard Schmalhofer wrote:
>Hi,
>
>I have started to work on some of the missing ops for the Resizable*Array
>PMCs.
>I noticed that, unlike the Array and PerlArray PMC, they currently do not
>use the functionality from src/list.c.
>This means that a ResizablePMCArray cannot be broken up in chunks and
>
> set P0, .ResizablePMCArray
> P0[1000] = 1000
>
>causes a lot of memory allocation.
>
>Is there a design reason for not having a chunked implementation?

At this point, I think a chunked implementation is actually
significantly sub-optimal. It makes sense for large or sparse arrays.
Most of the arrays we'll be dealing with are going to be smallish,
and the list stuff is unneeded overhead. The arrays can, if we want
to get clever, switch to a chunked representation when things get big
enough.

I think I'd rather the resizeable and fixed arrays went with a
non-chunked scheme by default, rather than a chunked one. We'd pick
up some speed on array access that way in the majority of cases.
--
Dan

--------------------------------------it's like this-------------------
Dan Sugalski even samurai
d...@sidhe.org have teddy bears and even
teddy bears get drunk

Bernhard Schmalhofer

unread,

Oct 21, 2004, 12:34:37 PM10/21/04

to l...@toetsch.at, Bernhard Schmalhofer, perl6-i...@perl.org

Leopold Toetsch wrote:

>>Is there a design reason for not having a chunked implementation?
>
> Then you could use Array/PerlArray anyway (modulo the PerlUndef).

As I understood it, the language specific PMCs are planned to become
dynamic classes and are supposed to move to their respection languange/*
directory.
So that would leave the standard PMCs, from pdd17, in the core Parrot
distribution. I'm not sure where the Array PMC stands there. My idea was
that PerlArray should inherit from ResizablePMCArray.

This would make the Array PMC obsolete. Or a new incarnation of the
Array PMC could serve as an abstract PMC.
I imagine a 'extends' hierarchy of PMCs like:

I left out the Boolean, String, Env, ..... PMCs.
This also depends wether there will multiple inheritance for C-Code
generation with 'pmc2c2.pl'.

>>One thing, that is propably hard to cover, is the method "sort" inherited
>>from FixedPMCArray. It looks like 'qsort' needs a continous piece of memory
>>for sorting.
>
> Well, qsort can't remain for various reasons. The main one is that it
> doesn't allow additional params to be passed to the sort function.
> Currently these are static globals, which makes the sort non-reentrant.

So I don't have to worry about it.

> For performance reasons we might need some sort/merge algorithm anyway
> and then it can work through chunks too.
>

CU, Bernhard

--
**************************************************
Dipl.-Physiker Bernhard Schmalhofer
Senior Developer
Biomax Informatics AG
Lochhamer Str. 11
82152 Martinsried, Germany
Tel: +49 89 895574-839
Fax: +49 89 895574-825
eMail: Bernhard.S...@biomax.com
Website: www.biomax.com
**************************************************