In most unix systems, and in my case most relevantly in linux, there's
a very useful command-line utility (or, in many cases, a shell built-in
command) called "time". This utility can be used to very accurately
measure how much system-time, user-time and overall time a program takes
during its execution. This is extremely useful for example when comparing
the speed of several versions of a program.

  Now, what I would also like to have is a similar utility or built-in
command which tells be the peak memory usage of a program. I want to know,
for example, if an optimization I made in a program really saved a relevant
amount of memory or not. Sounds rather simple, doesn't it?

  Well, to my amazement there doesn't seem to be any such utility in
existence for unix or linux in particular.

  There are tons of ways of seeing how much a program is *currently*
taking. For example, you can use utilities like "top", "pmap", "vmstat"
and "ps" for this purpose. They all can tell how much memory a program
is taking.

  However, those are no good. If a program runs just for a few seconds,
constantly allocating more and more memory, those utilities are completely
useless. Even if you get to run them during the execution of the program,
you only get a completely random result: They show you how much memory
the program is using *at that moment*. They don't show you the overall
peak memory usage of the program. The program may well allocate humongous
amounts of memory more after you took a look at it with any of those
utilities. They don't tell you anything relevant. (Those utilities are
only useful for programs which are running for a long time, and you want
to take a look on how much they are consuming memory currently.)

  What I don't understand is why there can't be any such utility.
Given that utilities like "top" & co. can measure the memory usage
of a process, it would sound quite plausible that it would be rather
easy to make a utility similar to "time" which measures the peak memory
usage of a program.

  But no. There doesn't seem to be any such program. I'm completely
puzzled about why this is so.

  (And before anyone suggests using the gnu version of "time", don't
bother: It doesn't work. It always gives 0 as the amount of memory used,
which is documented to happen when it doesn't support measuring that.)

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
>   But no. There doesn't seem to be any such program. I'm completely
> puzzled about why this is so.

For one thing, there's no unified performance measurement/reporting 
mechanisms in Linux. And in the original versions of Linux, you really 
could only fit a tiny number of programs in memory at once. (The reason 
fork() works the way it does is it was implemented originally (as in 
Version 7) as "swap out this process, but don't clear it out of memory 
afterwards.)

So there's no good way of seeing how much your peak memory is, or your 
disk I/O rate, or how much network bandwidth you're taking up, because 
you'd have to build each of these reporting infrastructures from 
scratch. There's no "performance monitor" kind of thing where you could 
implement *just* the memory watcher and already have the libraries to 
track peak, average, etc.

-- 
   Darren New / San Diego, CA, USA (PST)
     "That's pretty. Where's that?"
          "It's the Age of Channelwood."
     "We should go there on vacation some time."

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> So there's no good way of seeing how much your peak memory is, or your 
> disk I/O rate, or how much network bandwidth you're taking up, because 
> you'd have to build each of these reporting infrastructures from 
> scratch. There's no "performance monitor" kind of thing where you could 
> implement *just* the memory watcher and already have the libraries to 
> track peak, average, etc.

  Yet there are plenty of resource monitors which can show cpu usage,
bandwidths, memory usage, disk usage, and lots of info on a per-process
basis ('top' being the basic example).

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
>   Yet there are plenty of resource monitors which can show cpu usage,
> bandwidths, memory usage, disk usage, and lots of info on a per-process
> basis ('top' being the basic example).

But that's peeking into the current system tables. Seeing what it is 
right now is easy. Reliably recording it moment by moment needs more, 
methinks.

If saying "hey, I just called sbrk() for another page of memory" or "I 
just did six I/Os to satisfy a select query" was as easy as sending 
something to syslog, I expect a lot more libraries would implement those 
sorts of measurements. As it is, there's no good place for the C runtime 
(for example) to record the max memory used, and no easy way to look at 
it when it's done. So adding this capability needs the implementor not 
only to record how much memory was used, but to write a program to 
display the histogram, to decide on a file format to use, to build the 
configuration subsystem to say what file it should go into, etc. And if 
it's something in the kernel, you have to probably build a device driver 
to turn it on and off, etc.  Probably seems like a lot of work.

Of course, I'm just guessing at a reason.

Say, did you try things like Purify? Shouldn't that be able to track it, 
since it replaces malloc and free?

-- 
   Darren New / San Diego, CA, USA (PST)
     "That's pretty. Where's that?"
          "It's the Age of Channelwood."
     "We should go there on vacation some time."

Post a reply to this message

Darren New a écrit :
> Say, did you try things like Purify? Shouldn't that be able to track it, 
> since it replaces malloc and free?
> 

What's really strange is that valgrind, which tracks everything having 
to do with memory, does not provide the peak usage in the output. It's 
on the graph written by massif, one of the tools, but there is no 
numerical value.

Post a reply to this message

Vincent Le Chevalier <gal### [at] libertyallsurfspamfr> wrote:
> What's really strange is that valgrind, which tracks everything having 
> to do with memory, does not provide the peak usage in the output. It's 
> on the graph written by massif, one of the tools, but there is no 
> numerical value.

  valgrind only counts how much memory is *explicitly* allocated by
the program (eg. with malloc calls). It doesn't show the *real* amount
of memory used by the object. The real amount may be larger for several
reasons, such as each 'malloc()' or 'new' call causing extra 16 bytes to
be allocated, the memory page size in linux being 4 kilobytes, etc etc.
Also memory fragmentation may well cause the program to allocate
considerably more memory than it's really using, and valgrind won't
show you that because it only counts explit mallocs and frees. (The real
amount of memory used can only be examined with system calls because
it's the OS which is book-keeping the real amount of memory allocated for
each process.)

  Examining brk calls with strace gets much closer to the truth, but
it may not be a completely sure way of telling the real amount of memory
the process is using (as some memory may be allocate with mmap2).

-- 
                                                          - Warp

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> If saying "hey, I just called sbrk() for another page of memory" or "I 
> just did six I/Os to satisfy a select query" was as easy as sending 
> something to syslog, I expect a lot more libraries would implement those 
> sorts of measurements.

  I'm not exactly sure what you mean by that. Examining the brk() system
calls made by a process is quite easy using 'strace' (or in some unix systems
'truss').

  Examining brk() calls can actually be used to get a pretty accurate figure
of the memory usage of the program, but it's not always that unambiguous.
Basically you would need to know what is the base address used by the
program so that you can substract the largest value of brt() from that.
Usually the first brk() request made by the process is a good bet, but
the result may still be a bit biased. Another way is to put some debug
print at the beginning of main() and start counting brk() calls from
there, which gives the amount of memory allocated by the program after
its main() has started. (This can be done easily in the program itself
by making an sbrk(0) call at the beginning of main() and another at the
end and calculating their difference, which will give the amount of memory
in bytes that the program has allocated.)

  OTOH, only examining brk() calls is not the whole story and doesn't
always give the real amount of memory allocated by the program. This is
because libc sometimes makes cleverl tricks using mmap2() to allocate
memory, bypassing brk(). Thus any memory allocated that way will be
missed if we examine only brk().

  But anyways, for my purposes it would be enough to get whatever tools
like 'top' are using to measure the memory usage of the program.

> Say, did you try things like Purify? Shouldn't that be able to track it, 
> since it replaces malloc and free?

  Simply examining mallocs and frees performed by the program does not
give an accurate figure. The actual amount of memory used by the program
may be significantly larger. For example memory fragmentation can cause
this quite prominently.

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
> Darren New <dne### [at] sanrrcom> wrote:
>> If saying "hey, I just called sbrk() for another page of memory" or "I 
>> just did six I/Os to satisfy a select query" was as easy as sending 
>> something to syslog, I expect a lot more libraries would implement those 
>> sorts of measurements.
> 
>   I'm not exactly sure what you mean by that. Examining the brk() system
> calls made by a process is quite easy using 'strace' (or in some unix systems
> 'truss').

I mean that if programmers didn't need to build the entire reporting 
infrastructure, but could instead just "add points to the graph", I 
expect programmers would be more likely to include the code to do so.

The comparison with syslog was meant to say: If every programmer had to 
recreate the entire syslog deamon and reporting infrastructure, you'd 
have far fewer programs capable of doing distributed monitoring. As it 
is, all the program needs to do is drop a UDP packet, and the whole 
"where does it go, who sees it, and do I send a page" thing is already 
written for it.

If there was a system call that said
   add_to_counter("MemoryPagesUsed", 1)
   add_to_counter("MemoryPagesUsed", -1)
already written, you'd probably see a version of the C runtime library 
with a switch that would invoke those calls within malloc and free.

Plus, you'd probably see a bunch more servers reporting the same way: 
pages served per second from Apache, queries answered by MySQL, etc. 
Rather than (for example) having to parse Apache web logs to figure that 
out for Apache, and someone else's logs to figure it out for *that* 
program, and etc.

>   But anyways, for my purposes it would be enough to get whatever tools
> like 'top' are using to measure the memory usage of the program.

Yah. I was kind of disappointed when I was running "top" and seeing (for 
example) several programs blocked, nobody running, no disk I/O, no 
network I/O, etc.  vmstat turned out to tell the real story, but not on 
a per-processes basis.

>   Simply examining mallocs and frees performed by the program does not
> give an accurate figure. The actual amount of memory used by the program
> may be significantly larger. For example memory fragmentation can cause
> this quite prominently.

Fair enough. :-)  I wasn't sure just what you were after.

-- 
   Darren New / San Diego, CA, USA (PST)
     "That's pretty. Where's that?"
          "It's the Age of Channelwood."
     "We should go there on vacation some time."

Post a reply to this message

Sounds like a job for the kernel.  Doesn't the kernel support logging?

-- 
...Ben Chambers
www.pacificwebguy.com

Post a reply to this message

Warp wrote:
> 
>   Now, what I would also like to have is a similar utility or built-in
> command which tells be the peak memory usage of a program. I want to know,
> for example, if an optimization I made in a program really saved a relevant
> amount of memory or not. Sounds rather simple, doesn't it?
> 
>   Well, to my amazement there doesn't seem to be any such utility in
> existence for unix or linux in particular.
> 
>   There are tons of ways of seeing how much a program is *currently*
> taking. For example, you can use utilities like "top", "pmap", "vmstat"
> and "ps" for this purpose. They all can tell how much memory a program
> is taking.
> 

I believe that in the proc directory you can dig down to get to the 
actual process information.
I would check to see if there is a 'file' for the specific process that 
reports the current memory usage.
I know that it is these files that ps uses for its reporting.

Just a thought on a direction that could give you what you are after.


Tom

Post a reply to this message

Tom Austin wrote:
> I would check to see if there is a 'file' for the specific process that 
> reports the current memory usage.

The problem with that approach is you're just polling. There's no good 
way to find the max memory usage if you only use that much for 1/100th 
of a second.

-- 
   Darren New / San Diego, CA, USA (PST)
     "That's pretty. Where's that?"
          "It's the Age of Channelwood."
     "We should go there on vacation some time."

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> Tom Austin wrote:
> > I would check to see if there is a 'file' for the specific process that 
> > reports the current memory usage.

> The problem with that approach is you're just polling. There's no good 
> way to find the max memory usage if you only use that much for 1/100th 
> of a second.

  This is a real bummer. I would have wanted accurate memory usage
statistics for the small project I have been making, but it seems to
be impossible.

  If anyone happens to be interested, it's this:
http://warp.povusers.org/FSBAllocator/

  From all the tests I have made regarding the memory usage I'm pretty
confident that with the list-of-ints example my allocator uses half the
memory as the default allocator of libc, but I can't tell for sure
because of all these unknowns, as well as some erratic behavior I noticed
during my tests. Thus I couldn't add this statistic to the page,
unfortunately.

  It's interesting, though. Sometimes C++ *can* actually be slower than
some other languages, and the reason may be in the memory allocator used
by the compiler (or, more specifically, by the standard C libraries).
It's not really so much a fault of C++ per se, but more a fault of the
system library tasked on the memory management.
  Using a more efficient memory allocator can cause amazing speedups, as
I wrote on that page.

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
> It's not really so much a fault of C++ per se, but more a fault of the
> system library tasked on the memory management.

Yah.  It *can* be a fault of the standard for a language, tho. For 
example, doesn't C++ require that "destroy" and "free()" basically do 
the same things to the memory allocation? In the sense that "new" isn't 
allowed to look at the type and (say) overallocate a block and do its 
own sub-block management type stuff?  I.e., in the sense that the 
standard library isn't allowed to do some of the stuff you might do 
yourself by overriding "new"?

>   Using a more efficient memory allocator can cause amazing speedups, as
> I wrote on that page.

That's one of the ways GC can be faster than manual memory management. 
Many, many memory management libraries really suck bigtime, while a 
tremendous amount of time is spent making GC fast.

-- 
   Darren New / San Diego, CA, USA (PST)
     "That's pretty. Where's that?"
          "It's the Age of Channelwood."
     "We should go there on vacation some time."

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> >   Using a more efficient memory allocator can cause amazing speedups, as
> > I wrote on that page.

> That's one of the ways GC can be faster than manual memory management. 
> Many, many memory management libraries really suck bigtime, while a 
> tremendous amount of time is spent making GC fast.

  I don't see how GC would help that at all.

  The problem with the default allocator is that it has to be prepared to
allocate blocks of *any* size, and it should do it as memory-efficiently
as possible (ie. wasting as little memory as possible). This makes it
pretty complicated. It needs quite a lot of bookkeeping data, and keeping
track of free blocks of memory is rather complicated.
  This is even further complicated by the fact that the default memory
allocator must be thread-safe. This means that if two threads try to
allocate memory at the same time, the allocator must use mutual exclusion.
Mutual exclusion locks cause considerable overhead. In single-threaded
programs this overhead is useless, but there isn't an easy way around it.

  Why would GC help this? Even GC'd memory must be prepared to allocate
blocks of any size, and it must be thread-safe. I don't think GC would
help these problems.

  If I'm not completely mistaken, the major reasons why my allocator is
so much faster than the default allocator in libc is because it uses a
lot less bookkeeping data (because it only allocates blocks of fixed
size), the bookkeeping is much simpler and a lot faster to manage, and
my allocator is not thread-safe (which can be a big minus in some cases,
of course).

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:

>   The problem with the default allocator is that it has to be prepared to
> allocate blocks of *any* size, and it should do it as memory-efficiently
> as possible (ie. wasting as little memory as possible).

I suspect this latter part is what makes it slower than it could be. Not 
that it's bad. It's just a trade-off.

>   This is even further complicated by the fact that the default memory
> allocator must be thread-safe.

Yeah. If you're willing to over-allocate, you can reduce the contention.

> Mutual exclusion locks cause considerable overhead. In single-threaded
> programs this overhead is useless, but there isn't an easy way around it.

Linking with a different allocator that doesn't try to lock anything? 
:-) Of course, you'd have to *tell* it you're thread-safe. And of 
course, threads aren't part of the language (are they?) while memory 
allocation is, so you're kind of hosed right there.

In Ada, for example, you could have a different heap for each thread, so 
you don't get that kind of lock contention, because Ada knows about 
threads. (And IIRC, the language rules forbid returning a pointer 
allocated in one thread and using it in another, which I guess is the 
bit that actually helps.)

>   Why would GC help this? Even GC'd memory must be prepared to allocate
> blocks of any size, and it must be thread-safe. I don't think GC would
> help these problems.

Allocations can be much faster, because you don't go looking for free 
space until you run out of space.  If you tend to allocate a bunch of 
stuff, then free almost all of it, assuming you don't have 
finalizers/destructors/whateveryoucallthem to worry about, you can clean 
up lots of memory without ever looking at it. (This is not uncommon in 
languages where everything is actually a heap-based object, like 
Smalltalk. You can measure down in the single-digit-percentages of 
objects that last more than a couple of seconds on such systems. Of 
course, in a hybrid system like C++ or Ada or something, one probably 
makes much less garbage because most of the temporary stuff *is* on the 
stack.)

So, no running thru free chains to find memory, and no need to touch 
free memory when you free it, are the primary sources of speed. I.e., 
except for the GC itself, it's much simpler code than malloc and free.

Erlang, for example, has a bunch of different algorithms and a bunch of 
different allocators it switches between on the fly, depending on the 
behavior of your programs. And if I understand correctly, it'll use 
different allocators for different threads in the same process. Since 
threads don't share heaps (at least, not the fast-changing heaps) the 
threading problem isn't there. (They do apparently share heaps of large 
binary objects, as well as the "in-memory database" tables, which are 
also GCed.) And apparently it's too expensive to actually track which 
executable codes are pointed to from the stack, so you can only have two 
versions of the same code at the same time, and if you purge the old 
version, any process running the old version gets aborted first. But 
otherwise, you could just use the return addresses to keep the 
executable code live, except for the inefficiency of that.

So Erlang winds up with stuff like this,
http://erlang.org/doc/man/erts_alloc.html
because it can tell what type it's allocating for. :-) Which is why I 
thought it's a shame the C++ standard says it's essentially not allowed 
to take advantage of type information in "new". Of course, Erlang is 
instrumented out the wazoo, because it's designed for systems you never 
ever turn off, so you really do want to get messages if some program 
starts using too much memory.

>   If I'm not completely mistaken, the major reasons why my allocator is
> so much faster than the default allocator 

Please understand that I wasn't commenting specifically on your 
allocator. Earlier you asked some stuff about GC, so I thought I'd just 
mention some generic GC wisdom here. Nothing in this thread should 
specifically be about any particular implementation of GC or manual 
allocators.

-- 
   Darren New / San Diego, CA, USA (PST)
     "That's pretty. Where's that?"
          "It's the Age of Channelwood."
     "We should go there on vacation some time."

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> >   Why would GC help this? Even GC'd memory must be prepared to allocate
> > blocks of any size, and it must be thread-safe. I don't think GC would
> > help these problems.

> Allocations can be much faster, because you don't go looking for free 
> space until you run out of space.

  So GC is basically a selfish and greedy memory allocation engine which
cares only about itself, not anything else in the same system which might
have some use for that wasted memory.
  (Not that this would be anything new to me.)

  Doesn't this also mean that the GC runs a lot more often than would be
strictly necessary? Isn't that kind of counter-productive? Not only is
memory wasted (and thus away from other processes), but part of the speed
benefits in doing so are lost by having to run GC sweeps more often.

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
>   So GC is basically a selfish and greedy memory allocation engine which
> cares only about itself, not anything else in the same system which might
> have some use for that wasted memory.

You could say it's a time-space trade-off.  You know, I almost never 
have a situation where I have two programs running and I'm paging 
because of it. :-)

>   Doesn't this also mean that the GC runs a lot more often than would be
> strictly necessary? 

Assuming you mean "allocating everything on the heap" when you say 
"this"....

> Isn't that kind of counter-productive? 

Only if your language has a stack and isn't functional and is 
single-threaded, I suppose. If your language definition is that the 
stack frames are stored on the heap (for, say, closure purposes), or you 
need to allocate a separate stack of some size for each thread anyway, 
or you tend to overwrite the same memory address with lots of different 
things at different times (unlike, say, LISP, where you tend to build 
new structures reusing parts of old ones instead of overwriting what you 
already have), then allocating lots of short-lived stuff on the heap 
makes sense.

Of course, systems like Smalltalk *do* really and truly have a stack 
(now), exactly for performance reasons. It just doesn't look that way, 
because it'll copy stack frames into the heap if you try to access them 
as "objects".  (Then again, Smalltalk didn't have conditional 
statements, either, in the semantics of the language. Just messages sent 
to booleans along with a couple blocks of text, and a method dispatch 
that evaluated the first block in the True class and the second block in 
the False class, which I thought was pretty cool. :-)

 > Not only is memory wasted (and thus away from other processes),

Remember that the original GC stuff was done on systems (Lisp, 
Smalltalk, etc) where the interpreter *was* the OS, so "taking away from 
other processes" doesn't always make sense.

But yes, some memory is "wasted" for some meaning of the word "wasted". 
Not unlike stack space is "wasted" if you're not about to overflow the 
stack.

It's also "wasted" if you are willing to spend more time on expert 
programmers who never make a mistake and hence never corrupt memory, 
rather than spending more money to buy some RAM. And indeed, when RAM is 
expensive (like in embedded devices), one tends not to see too many 
GC'ed systems.

And with some OS help, you can actually get pretty decent performance 
during collections. The ability to mark pages "manually" to say which 
are more likely to be needed soon, the ability to trap writes to 
particular pages so you can mark them as "the GC will need to examine 
this on the next sweep", the ability to pre-fetch paged-out pages while 
you're processing this one (i.e., read-ahead for page faults), etc.

> but part of the speed
> benefits in doing so are lost by having to run GC sweeps more often.

Running GCs too often is indeed a performance-limiting problem. That's 
one of the reasons that people writing collectors spend so much time 
trying to make them fast, and why there are so many different types of 
collectors (compared to, say, only a couple different kinds of stacks).

-- 
   Darren New / San Diego, CA, USA (PST)
     "That's pretty. Where's that?"
          "It's the Age of Channelwood."
     "We should go there on vacation some time."

Post a reply to this message

Darren New wrote:
>> Isn't that kind of counter-productive? 
> 
> Only if your language has a stack and isn't functional and is 
> single-threaded, I suppose.

And yes, I agree, Java in this respect is kind of suckful, 
efficiency-wise. I think it's at least as much because they're trying to 
be portable and dynamic loading.

-- 
   Darren New / San Diego, CA, USA (PST)
     "That's pretty. Where's that?"
          "It's the Age of Channelwood."
     "We should go there on vacation some time."

Post a reply to this message