Do you use a garbage collector?

[Juha Nieminen]

OOP might have distracted minds from some other approaches
that might have been even more beneficial. But we will never
learn about such alternative histories, so we can not compare
history to them.

Some features are attributed to OOP, but actually are also
parts of other non-OOP approaches. For example, encapsulation
and a compound entity of related operations one data are
features of an ADT (abstract data type). So, one also has to
give a specific definition of OOP and non-OOP before
discussing its effects on productivity.

It seems to me like you are arguing that OOP is not the *only*
programming paradigm which improves productivity. However, that was not
the point. The question was whether OOP has increased productivity or
not. "Also this other paradigm has the same features as OOP" doesn't
really say "OOP does not increase productivity". It just says "OOP is
not the only thing that increases productivity".

 

[Silvio Bierman]

int main(int argc, char *argv[]) {

clock_t start=clock();
for (int i=0; i<=10000000; i++) {
Test *test = new Test(i);
if (i % 5000000 == 0)
cout << test;
}

If I add delete test; to this loop it gets faster. huh? what the
exaplanation for this?

2156 ms

and after I add delete test; to the loop

1781 ms

why is that?

Because new in C++ does NOT directly call an OS allocation function. C++
internally uses something similar to malloc/free from C which are memory
management functions that use OS allocation functions as its base but
keeps a self-maintained heap of, allocated at the OS level but
unallocated at the application level, free blocks.

If you keep allocating with new without using delete the OS allocations
have to be done. If you use delete the block goes into the free-blocks
heap and is probably returned immediately with the next new call. You
probably see the same memory address each time through the loop.

Regards,

Silvio Bierman

 

[Mirek Fidler]

If there is not enough memory on stack, you don't have a choice.

Is is not about stack only.

You
have to dynamically allocate memory sometimes.

Yes, but much less

I changed the loop to

for(int i = 0; i < 15; i++)
DeleteTree(CreateTree(22));

Now you don't have a choice, or do you?

this requires at least 68 MB on U++

Time: 4562 ms (U++)
Time: 27781 ms (g++)

java -server -Xms1024m -Xmx1024m

Time: 3578 ms (max memory I saw was on 300 M -- but at least it
finished 7 times faster than g++ ...

with -Xms75m -Xmx100m the time is around: 9969 ms

On Jet, 2344 ms (wow, that was fast but memory peak was 600 MB!)

IMO, manual management still wins...

Mirek

 

[Mirek Fidler]

All Java has to do is add N (the size of the object) to a counter and
zero out the object.

Does it mean Java allocator is serialized? Well, that would be a
problem... Good C++ allocators are not locked for the fast path.

In C++ it also has to look for a hole the right
size and record it is some sort of collection.

Which for the fast path is (or should be) equivalent of about 20 asm
ops.

What you basically need to do is to divide the size by "small
quantum" (e.g. 16) to get the bucket type, then unlink single item
from the bucket. Allocation finished.

Mirek

 

[Mark Thornton]

Does it mean Java allocator is serialized? Well, that would be a
problem... Good C++ allocators are not locked for the fast path.

(Ignoring for now that there isn't one Java allocator), typically there
is a per thread area so these counters do not need locks.

Mark Thornton

 

[Mirek Fidler]

Running this version on VC++ and g++: 43718 ms and g++ 46890 ms

that is 5 to 6 times slowe than in U++

Well, that actually proves my point, does not it?

(The one about average implementation of standard C++ library being
the crap and about zero effort invested into manual allocators).

Mirek

 

[kepeng]

It's so unfair!

Razii $B<LF;!'(B

Well, my friend, I have proven you wrong. Razi has been victorious
once again


Time: 2125 ms (C++)
Time: 328 ms (java)


--- c++--

#include <ctime>
#include <cstdlib>
#include <iostream>

using namespace std;

class Test {
public:
Test (int c) {count = c;}

This is assignment after initialization.
It should be like this:
Test(int c) : count(c) {}

virtual ~Test() { }
int count;
};

int main(int argc, char *argv[]) {

clock_t start=clock();
for (int i=0; i<=10000000; i++) {
Test *test = new Test(i);
if (i % 5000000 == 0)
cout << test;

The memory you allocated is not released, so every new() is actually a
allocation operation to libc.
When the heap is empty, a new page of memory is allocated from OS.

}
clock_t endt=clock();
std::cout <<"Time: " <<
double(endt-start)/CLOCKS_PER_SEC * 1000 << " ms\n";
}

-- java ---

import java.util.*;

class Test {
Test (int c) {count = c;}
int count;

public static void main(String[] arg) {

long start = System.currentTimeMillis();

for (int i=0; i<=10000000; i++) {
Test test = new Test(i);
if (i % 5000000 == 0)
System.out.println (test);

After this and assign a new object to the 'test', the 'test' is no
longer ref to the older object.
So the older object is free to release.
Once the java VM's heap is empty, a gc() is called and done. The
memory for the older objects is free for allocation again.
In this example, the java VM calls OS' memory page allocation once and
then never need to alloc again.

 

[Roedy Green]

Java can use a multitude of allocation techniques.

Yes, in theory, but since Java uses garbage collection which nearly
always would imply it can later move objects, it can get away with a
very simple, very rapid allocation algorithm, namely adding the length
of the object to the free space pointer. In Java there are all kinds
of short-lived objects created. It makes sense to allocate them as
rapidly as possible.

In C++, objects typically don't move, so the allocation algorithm has
to take more care with where it places them.

 

[Roedy Green]

How does research hurt me, or anybody else?

It is not what you are saying, but HOW you are saying it. You come
across like a prosecutor crossed with a bratty five year old.

 

[Bo Persson]

It's so unfair!

But it doesn't matter much.

Razii $B<LF;!'(B
This is assignment after initialization.
It should be like this:
Test(int c) : count(c) {}

A decent optimizer will recognize this and generate identical code for
int types.

virtual ~Test() { }
int count;
};

int main(int argc, char *argv[]) {

clock_t start=clock();
for (int i=0; i<=10000000; i++) {
Test *test = new Test(i);
if (i % 5000000 == 0)
cout << test;

The memory you allocated is not released, so every new() is
actually a allocation operation to libc.
When the heap is empty, a new page of memory is allocated from OS.

The really unfair thing is that you would never ever do anything like
this in C++. Why would any application allocate ten million int sized
objects separately?

std::vector<Test> test(10000001);


Bo Persson

 

[Jerry Coffin]

[ ... fully connected network for deallocation ]

The design exhibits great performance, except when presented with a user
program that persistently creates and destroys multiple threads. This can be
fairly significant downside wrt creating general purpose tools... ;^(

I wonder whether it isn't better to just avoid this problem. Rather than
always creating and destroying threads on demand, create a thread pool.
When the user wants a thread, they're really just allocating the use of
the thread from the pool (i.e. you give that thread the address where it
needs to start executing, and send it on its way). When they ask to
delete a thread, you just return it to the pool. If they ask for a
thread and the pool is empty, then you create a new thread. You could
then add a task for the thread pool to execute occasionally that trims
the thread pool if it stays too large for too long.

Obviously, this goes a bit beyond pure memory management, but not really
by a huge amount -- it's still definitely in the realm of resource
management.

[ ... ]

You have the 100% right idea overall.

I'm assuming you mean that since nearly all the data is constant on a
per-allocator basis, you just create a single information block per
allocator, then each allocated block just carries a pointer to the
information block in its associated allocator.

If you want to badly enough, you can reduce the per-block overhead even
more than that though -- instead of storing a pointer, store only an
index into a vector of information blocks. With some care, you should
even be able to eliminate that -- for example, have N bits of the
addresses produced by each allocator unique from the range used by any
other allocator. In this case, retrieving the allocator for a specific
block consists of a shift and mask of the block's address. Better still,
this is immune to the code using the block overwriting data by writing
to addresses outside the allocated space.

Obviously this latter method applies better to 64-bit addressing, but
with a bit of care could undoubtedly be applied for quite a few 32-bit
situations as well.

 

[Roedy Green]

AFAICT, in a sense, you don't what your talking about. Explain how you
synchronize with this counter? Are you going to stripe it? If so, at what
level of granularity? Java can use advanced memory allocation techniques.

All I said was JVMs can for the usual case use an extremely fast
simple memory allocation mechanism. They just peel the next N bytes
off the free space pool. They don't have to search around for the
right sized hole. GC/memory allocation is the subject an astounding
amount of cleverness and creativity. I get people started on that
exploration with my essay at
http://mindprod.com/jgloss/garbagecollection.html

I had no intention of claiming this was all there was to memory
allocation or garbage collection.

I am not on trial. So get stuffed.

 

[Roedy Green]

These questions are meaningless and irrelevant.

Several simple ones, but I have not written a Java JVM. I wrote BBL
Forth which was twice as fast as the competition, so I am not a
complete newbie.

 

[Roedy Green]

Roedy! Not Reedy... CRAP!

Don't worry. Nearly everyone gets it wrong. Even my mother sometimes
called me "Roger".

 

[Roedy Green]

to increment a pointer location off of common base memory.

The initial discussion was about how Object.hashCode could be
implemented. That COULD be done with a global counter. You would
need simple synchronisation (e.g. an atomic memory increment)
instruction to share it among threads.

In a similar way you can do a fast object allocation simply by
incrementing the free space pointer, either one per thread with
separate pools or with a synchronised global one.

The two discussions became muddled and intertwined. I think also there
was confusion between what you might write IN Java vs assembler code
inside the JVM to handle to low level details of object allocation.

 

[Roedy Green]

(Ignoring for now that there isn't one Java allocator), typically there
is a per thread area so these counters do not need locks.

Also consider the JVM does not have to use heavyweight Java-type
object locks. It can get away with much more light-weight techniques.
It can "cheat". This object allocation code has to be blindingly fast,
and all sorts of techniques you would never dream of using in
application code become legit.

All you have to do is read one GC paper to see this IS rocket science.
We can only scratch the surface in these discussions.

 

[Roedy Green]

Heap compaction is nothing all that special. Its certainly not tied to a GC.
Not at all.

You can have heap compaction without GC, e.g. the original Mac with
its explicit handle allocations in Pascal. But have you ever seen a
GC system without heap compaction? Perhaps someone cooked one up as
an add-on to C++?

 

[Mark Thornton]

Also consider the JVM does not have to use heavyweight Java-type
object locks. It can get away with much more light-weight techniques.
It can "cheat".

JVM's often use highly optimised locking techniques even for regular
objects (e.g. synchronized methods). In some cases they can even
eliminate a lock altogether via escape analysis. This gets done even for
a newbies code whereas a junior programmer trying to achieve similar
locking performance in C++ is unwise at best. Even 10 years ago, JVMs
adapted locking to suit the machine at run time (faster locking on
single processors than multi cpu systems).

Mark Thornton

 

[Juha Nieminen]

http://pastebin.com/f6bfa4d78 (C++ version)

In a Sun-Fire-V240 computer I was able to bring down the execution
time of that program from 24630 ms to 3990 ms by using my own (portable)
memory allocator. The maximum memory usage was something like 55 MB.

"java Test" in that same computer runs the java program in 4502 ms.
With "java -server -Xms170m -Xmx170m -XX:NewRatio=1 Test" it was
1828 ms.

 

[REH]

Testing the keyword "new"

Time: 2125 ms (C++)
Time: 328 ms (java)

Explain that. What I am doing different in java than in c++? Code
below..

What you are doing differently is not freeing the memory. Since you
are allocating gobs of memory, and not releasing it, the C++ version
will incur the cost of page faults, virtual memory access, disk
thrashing, etc. You are timing a lot more than just memory
allocation. Of course a lot of people use contrived examples like
this to prove their pet language is faster than another. What a waste
of time...

REH