deadly slow !!

Folks,

Add a method loose below.
It won't be harmful to your image just by add it, unless you invoke it
with unproper parameter.

SequenceableCollection>>codeBookOf: anInteger

        anInteger <= 0 ifTrue: [^self class new].
        ^anInteger = 1
                ifTrue:
                        [self collect: [:obj| self class with: obj ]]
                ifFalse:
                        [|newAnswerStream|
                        newAnswerStream := WriteStream on: (self class new: (self size
raisedTo: anInteger)).
                        (self codeBookOf: anInteger-1) do: [:oneSubAnswer|
                                self do: [:oneObjectToAdd|
                                        newAnswerStream nextPut: oneSubAnswer, (self class with:
oneObjectToAdd)]].
                        newAnswerStream contents]


This method is not a problem when anInteger is small.

Try, #(true false) codeBookOf: 3


It is a problem when anInteger is big. Try below after a good backup of
your image.


#(nil 0) codeBookOf: 25 "Number 25 maybe not be big enough for your
PC."


makes my PC(P-4 2.4GHz 512MB DDR ram) nearly stop!

Memory paging goes up to 1.2GB, and Dolphin.exe eats up to 380MB.
CPU usage goes up to 50% but soon or later it drops down to 2%.
That seems to me like the #codeBookOf: has been answered, and workspace
is idle.
But workspace is still hanging and memory allocation is still 1.2GB.
The answered object(Array) is not kept in a workspace variable so it
must have gone garbage collected right away(or 10 sec later). But still
1.2GB, hard disk is turning like as if it's going to blow.

As soon as I kill Dolphin.exe from process list, memory allocation
drops down to 550MB and disk rests in peace.


Can anyone explain this phenomenon?

Howard Oh wrote:

Of course, this will be slow. If this worked, you would have created a
collection of size 33,554,432 (2 raisedTo: 25). Each element in that
collection would have contained a 25 element collection. The amount of
space just for the pointers would be (33554432*4) + (33554432*25*4) =
3,489,660,928 bytes (plus a few more bytes for object headers, etc.).
Furthermore, since the algorithm isn't too efficient on how it computes
the arrays, you would have needed enough space to hold the #codeBookOf: 24.

You should think about the problem differently. The i'th item in the
collection is just the result "printing" i to base "self size" using the
items in the collection as your characters. For example, you could use
something like:

codeBookOf: anInteger at: anIndex
        | index current |
        index := anIndex - 1.
        current := OrderedCollection new: anInteger.
        anInteger
                timesRepeat:
                        [current addFirst: (self at: index \\ self size + 1).
                        index := index // self size].
        ^current

Then you can evaluate:

        Number fromString: '2r',
                (String withAll: ('01' codeBookOfSize: 32 at: 1234567))

This returns 1234566 since we are converting from Smalltalk's 1 based
indexing to a zero based scheme.


John Brant

John,

Your #codeBookOf:at: is really a great approach for avoiding wasting
memory for #codeBookOf:.
I will add your version right away except for the OrderedCollection
hard typing. I would like to give more flexibility to this method.

And your calculation seems to explain 380MB allocation well.

What is still not understood is why the big memory wont go away after
CPU usage becomes nearly zero, like for small parameters for
#codeBookOf: does.

Best Regards

Howard,

Well, you are running out of stack in the VM (quite why I'm not sure).
I don't know what the method is meant to do but you have a line in
there:

(self class new: (self size raisedTo: anInteger))

So, as a miniumm you are allocating Array objects with 2^25 + 2^24 +
2^23 etc objects in them. The first term alone is worth 130Mb and that
is even without the array being filled with any objects at all so
heaven knows how much actually gets allocated.

If I run the above, what I see is this. 50% CPU and memory usage going
up until it gets to around 75% the amount of physical RAM. At that
point CPU drops to 1%-2% but look at the disk light; the machine is
into paging and is hence disk-bound. This is why the CPU drops but the
algorithm is still continuing. If I leave it for another 5 mins or so,
the Dolphin process eventually collapses and writes a crash dump. So
the reason why the memory doesn't appear to go away for you is that you
aren't letting it "finish".

Whatever the algorithm does it needs to be coded differently, I'm
afraid. If you look at the crash dump that is written following the
crash you will see that it holds:

---
21:44:05 PM, 1/17/2006: Dolphin.exe caused an unhandled Win32 Exception
C00000FD
at 7C9377C9 in module 7C900000 (C:\WINDOWS\system32\ntdll.dll)
---

C00000FD is a stack overflow.

Best regards

--
Andy Bower
Dolphin Support
www.object-arts.com

Howard Oh wrote:

> Your #codeBookOf:at: is really a great approach for avoiding wasting
> memory for #codeBookOf:.
> I will add your version right away except for the OrderedCollection
> hard typing. I would like to give more flexibility to this method.
>
> And your calculation seems to explain 380MB allocation well.

It was 3,489,660,928 bytes (over 3GB). I believe Windows has a maximum
process size of 3GB.

> What is still not understood is why the big memory wont go away after
> CPU usage becomes nearly zero, like for small parameters for
> #codeBookOf: does.

Dolphin is still executing -- the CPU usage becomes nearly zero since
most of the time is spent by the OS paging to disk.


John Brant

Oh~

That explains.

I didn't know that memory paging was a CPU free operation.
I couldn't dare think a process so slow be CPU free.

Thanks everybody.

Best Regards

John,

I've refactored #codeBookOf: method by applying "MethodObject"
technique.
Subclassing SequencableCollection, named "CodeBook" which can answer to
#size, #at, #at:put:.
It works similar to Interval which is not a real collection but answers
properly to Collection protocol.

CodeBook>>size

        ^self codes size raisedTo: self codeLength


CodeBook>>at: anInteger

        ^((self multiQuoAndRem indexValue: anInteger-1)) collect: [:each| self
codes at: each ]


CodeBook>>at: anInteger put: anObject
        "Replace the element at index anInteger of the receiver with anObject.
        Intervals are immutable."

        ^self shouldNotImplement


CodeBook>>species

               ^Array


It can #do: #select: #collect:  without any heavy memory allocation,
although if i want the memory problem I can simply #asArray.  :-)
I'm very happy using CodeBook object.

Thank you very much for inspiring me John.

Best Regards