Subject: FVWM: Re: Memory Allocations

From: Dominik Vogt <[email-masked]>
Date: Fri, 22 Mar 2002 18:01:00 +0100

On Thu, Mar 21, 2002 at 11:31:46PM -0600, Dave Trollope wrote:
> Hi,
> 
> I recently downloaded and compiled fvwm2 for cygwin (having been using
> it on solaris for years) and was pleased to have it compile and run
> first time.
> 
> However, cygwin is a little slow and I was curious about the fvwm2
> source, so I downloaded it and decided to see if there was anything
> (even in the smallest way) to improve performance.
> 
> I think I found something that could improve general performance which I
> describe below, and would welcome feedback on whether to implement this.

Fvwm's speed depends to 90% or more on how the communication with
the X server is done.  All other effects of calling functions and
such only add very little to the CPU load.  Once I profiled fvwm
for ten minutes using gprof, and as far as I remember it did not
even consume one second of CPU time.  The things that slow it down
are file I/O and X server communication.

Talking about the code execution time, there is only one big
factor, the PositiveWrite() function that sends information to
the modules.  It can be called hundreds of thousands of times
during a busy work day.  Much effort has been made to optimize
that function.

> 1) I came across libs/safemalloc.c.
> 
> I was surprised that malloc was wrapped in a function like this since
> this is called whenever something is put on the (I think) event queue.
> Everytime I move the pointer from one window to another, launch tools
> etc, safemalloc is called. Wrapping malloc in a function is an overhead
> that will cause branches from the CPU cache probably when only one is
> necessary (the actual call to malloc itself).

I feel the added code size is not worth the effort most of the
time.  If individual functions are called ofthen from a certain
place it may be better to only optimize that place instead of all
the others where it isn't a problem.  For example, many of the
safemalloc() calls could be replaced with alloca(), even saving
the free() call.

> So #if 0'd out the safemalloc, safecalloc, saferealloc functions and
> recoded them as macros. E.G.
> 
> #define safemalloc(length) \
>    (malloc((length) <= 0 ? 1 : (length)) ? : (char
> *)alloc_failed("malloc",(length)))
> 
> The main advantage of this is that only one function call for each
> malloc is required (malloc itself) instead of two (safemalloc+malloc).
> ?: is supposed to be more efficient than if () but I'm not sure thats
> really true. If I could only disassemble the code.... Suggestions? One
> function call should reduce the number of branches (and therefore cache
> usage is improved).
> 
> The biggest disadvantage of this however is that the binary size
> increases because these decisions (length <= 0) are duplicated
> everywhere. Somewhat prone to casting issues of length.
 
> 2) The other related issue I found was that in some cases, dynamic
> memory is used for simple temporary use. Local stack arrays are much
> more efficient for this, however you don't want to restrict the size of
> the data being processed. I suggest that the majority of users will have
> little data and most optimisation can come from putting those into a
> local array, and only calling on safemalloc when handling larger data
> quantities.
> 
> libs/Graphics.c - do_relieve_rectangle
> 
> 
>   XSegment* seg,segarr[5];
> 
> ..
> 
>   if(line_width > 5)
> 
>     seg = (XSegment*)safemalloc(sizeof(XSegment) * line_width);
> 
>   else
> 
>     seg = &segarr[0];
> 
> ...
> 
>   if(line_width > 5)
> 
>      free(seg)
> 
> This would completely remove the malloc for 90% of users.

Yes, but what is the cost of the malloc?  RelieveRectangle is
perhaps called 20 times when a window changes focus.  I'd guess on
average you do not do this more than 5 times per minute, giving a
total of 6000 calls per hour.  I'd estimate that can easily be
done by any but the slowest machines in less than the tenth of a
second.  It is likely that more time could be saved by preventing
unnecessary calls to RelieveRectangle() in a single place in the
code since it requires communication over the network.

> I have half a dozen of these kind of things and a place or two where
> memset is called prior to a memcpy that overwrites the same block memset
> cleared.

Do you have a list of these?  Some of the memset() calls are
redundant.  Not all of these are bad thoug.  Some are merely
intended to prevent uninitialised elements of structures if new
members are added to the structures in the future.

> What do you think? While these are trivial changes, for a function that
> is called hundreds of times, even a small gain adds up. Shall I go ahead
> and make these changes? Perhaps as I grow more experienced with the
> fvwm2 source I can find some bigger issues.

I suggest this:

 - Find places where alloca() can be used instead of safemalloc.
   alloca is either a system function or a replacement from the
   fvwm library.  This eliminates the additional function call and
   even cuts down the chances of running out of memory.  A program
   that can't get more space on the stack is doomed to crash
   anyway.  It also reduces the chance of memory leaks.
 - Leave safemalloc as it is.  If there are specific functions
   that are called frequently, optimizing them is a good thing.
 - In many places there is code like
     ptr = safemalloc(size);
     memset(ptr, 0, size);
   This could be done faster and smaller with safecalloc().
 - For the big gain:  optimize the X calls.  Any call that
   contacts the X server needlessly causes delays.

And a comment on coding style:

 - Macros with code are evil.  Never use them.  Instead, you can
   inline the code (although it doesn't work with any compiler).

Bye

Dominik ^_^  ^_^

-- 
Dominik Vogt, email: [email-masked]
LifeBits Aktiengesellschaft, Albrechtstr. 9, D-72072 Tuebingen
fon: ++49 (0) 7071/7965-0, fax: ++49 (0) 7071/7965-20
--
Visit the official FVWM web page at <URL: http://www.fvwm.org/>.
To unsubscribe from the list, send "unsubscribe fvwm" in the body of a
message to [email-masked].
To report problems, send mail to [email-masked].

---

From: Dan Espen <[email-masked]>
Date: Fri, 22 Mar 2002 13:38:33 -0500

...
> members are added to the structures in the future.

I seem to remember at  least one unnecessary  memset added to avoid  a
Purify message about a UMR (unitialized memory read).

>    This could be done faster and smaller with safecalloc().

I know of  at least one  platform (C/370  MVS) where malloc/memset  is
faster  than calloc.   I  don't  know  why,  but  I believe  memset is
normally done inline on that platform.
This information was from a few years ago.

-- 
Dan Espen                           E-mail: [email-masked]
444 Hoes Lane  Room RRC 1C-214      Phone: (732) 699-5570
Piscataway, NJ 08854
--
Visit the official FVWM web page at <URL: http://www.fvwm.org/>.
To unsubscribe from the list, send "unsubscribe fvwm" in the body of a
message to [email-masked].
To report problems, send mail to [email-masked].

---

From: Dave Trollope <[email-masked]>
Date: Fri, 22 Mar 2002 21:30:10 -0600

Hi Dominik,

> are file I/O and X server communication.

I agree there are bigger fish to fry - this was my first look at fvwm source.
I thought it wiser to start with small steps.... I was thinking I would take a
look at XFree86 too sometime. I need to learn much about X primitives.

In terms of the performance - I felt like the system was more responsive in
cygwin with the modifications. Perhaps it was just my hopeful imagination!
What OS and CPU were you running when you profiled?

> during a busy work day.  Much effort has been made to optimize

AddToMessageQueue has 2 safemalloc calls - That equates to "hundreds of
thousands"*2 unnecessary function calls.

If you want to really optimise this, the first call could use malloc directly
dispensing with an unnecessary if (length == 0) as well as the function call.
Shouldn't do this on the second one because size could be any value.

> safemalloc() calls could be replaced with alloca(), even saving

Hmm that sounds like a good change to do. I will look at that.

> > [ code snipped ]
> Yes, but what is the cost of the malloc?

What does the cost matter when it can be reduced to 10% of the cost?

>  RelieveRectangle is
> second.

My only contention here is that if you don't need to do it, why do it. Even
tenths of seconds here and there add up.

>  It is likely that more time could be saved by preventing

Sounds like another promising avenue - I will take a look.

> redundant.  Not all of these are bad though.  Some are merely

The places where I'm thinking of use sizeof in both calls so if one misses a
new element, so would the other.

Here they are:

menus.c NewMenuStyle()
  tmpms = (MenuStyle *)safemalloc(sizeof(MenuStyle));
  memset(tmpms, 0, sizeof(MenuStyle));
  if (ms)
  {
    /* copy the structure over our temporary menu face. */
    memcpy(tmpms, ms, sizeof(MenuStyle));

The memset can be safely moved to the else leg of the if.

scanForColor()
  /* save instring in case can't find pixmap */
  save_instring = (char *)safemalloc(strlen(instring)+1);
  name = (char *)safemalloc(strlen(instring)+1);
  strcpy(save_instring,instring);

  /* Scan whole string        */
  for (txt = instring; *txt != '\0'; txt++)
  {
     ...
  }
  free(name);
  free(save_instring);

can become:
   int l = strlen(instring) + 1;
  /* save instring in case can't find pixmap */
  save_instring = (char *)safemalloc(l*2);
  name = save_instring + l;
  strcpy(save_instring,instring);

  /* Scan whole string        */
  for (txt = instring; *txt != '\0'; txt++)
  {
     ...
  }
  free(save_instring);

add_window.c setup_window_structure()

This memset isn't needed its only used in the else leg, and then its copied
over.:

  memset(&save_state, '\0', sizeof(FvwmWindow));

I thought I found more, but these were the ones I had written down.

>    contacts the X server needlessly causes delays.

I can easily attack the first three. My current inexperience with X limits the
last one, but I am interested in learning X development so I will look around
(I will look at the ReleiveRectangle calls first).

>    inline the code (although it doesn't work with any compiler).

Here we will have to agree to disagree. I believe macros with and without code
have their place. There are certain things that shouldn't be done in macros,
but I wouldn't call them evil!

Cheers
Dave

---

From: "Paul Smith"<[email-masked]>
Date: 23 Mar 2002 03:03:28 -0500

>> Yes, but what is the cost of the malloc?

  dt> What does the cost matter when it can be reduced to 10% of the cost?

This is an easy mistake to make when approaching optimization.  There is
often great benefit to _not_ optimizing code.  There is quite commonly a
tradeoff between "slow" methods that are clearer, simpler, more
reliable, etc., and optimized methods which are more abstract, less
obviously correct, harder to understand and modify in the future, and
potentially less robust.

Optimization is best done like this: write the code the most
straightforward way you can (XP uses the phrase "the simplest thing that
could possibly work", which I like).  Run it.  If it's slow, use some
kind of empirical evidence gathering method (profilers, etc.) to find
out where the bottlenecks are.  Fix the top bottleneck or two.  It's
almost always true that (a) you rarely guess right: the bottlenecks you
find are nothing like what you thought they'd be, and (b) optimization
follows the 80/20 rule: you can get 80% of the results for 20% of the
work, then it takes the other 80% of the work to get the last 20% of the
results.

Note I'm not saying that your ideas about how to speed up FVWM are
incorrect.  You may well be right.  But I personally would like to see
evidence before we complicate the code with special cases, etc.

My $0.02.

-- 
-------------------------------------------------------------------------------
 Paul D. Smith <[email-masked]> HASMAT--HA Software Mthds & Tools
 "Please remain calm...I may be mad, but I am a professional." --Mad Scientist
-------------------------------------------------------------------------------
   These are my opinions---Nortel Networks takes no responsibility for them.
--
Visit the official FVWM web page at <URL: http://www.fvwm.org/>.
To unsubscribe from the list, send "unsubscribe fvwm" in the body of a
message to [email-masked].
To report problems, send mail to [email-masked].

---

From: Dominik Vogt <[email-masked]>
Date: Sat, 23 Mar 2002 13:01:46 +0100

> work, then it takes the other 80% of the work to get the last 20% of the

Or to put it in a single sintence:

  Don't optimise before it hurts.

Bye

Dominik ^_^  ^_^

 --
Dominik Vogt, [email-masked]
Reply-To: [email-masked]
--
Visit the official FVWM web page at <URL: http://www.fvwm.org/>.
To unsubscribe from the list, send "unsubscribe fvwm" in the body of a
message to [email-masked].
To report problems, send mail to [email-masked].

---

From: Dominik Vogt <[email-masked]>
Date: Sat, 23 Mar 2002 12:59:22 +0100

> What OS and CPU were you running when you profiled?

Linux 2.2.something on a 400MHz Pentium 2.

> thousands"*2 unnecessary function calls.

Yeah, that's rather inefficient.  You can also merge
AddToMessageQueue into PositiveWrite and replace the two calls
to safemalloc with one to malloc.  I'll commit a patch.

[snip]

> What does the cost matter when it can be reduced to 10% of the cost?

I wanted to point out that the cost is low compared to other code.

> tenths of seconds here and there add up.

But on the other hand, the additional if's and the duplicate code
enlarge the binary and make the code harder to maintain.

> The memset can be safely moved to the else leg of the if.

Yup, I'll do that.

>   for (txt = instring; *txt != '\0'; txt++)

I'll use alloca instead and get rid of the free() alltogether.
 
> I thought I found more, but these were the ones I had written down.

I appreciate that work.  There are a lot of small enhancements
that can be made.  If you want to continue, please download the
latest snapshot or - better - the code from cvs (instructions for
cvs are on our home page).  Large parts of the code have changed
since 2.4.x and it can become tedious to port these patches to the
development branch.  Also, it's much easier to apply paches that
were created with diff:  Make a copy of the files you want to
change, edit them and run diff:

  $ cp foo.c foo.c.orig
  (edit foo.c)
  $ diff -u foo.c.orig foo.c > foo.patch

These patches can then be applied automatically with the patch
program.  (If the -u option is not supported by your diff version,
use -c instead).

> (I will look at the ReleiveRectangle calls first).

Basically the situation is this:  When X...() calls are made, the
commands are usually queued on the client until they are sent to
the server with XFlush or XSync is called.  This involved packets
going over the network - which is slower than the rest of the code
by order of magnitudes, even if the X server is on the same
machine.  So one goal would be to minimize the number of XFlush
and XSync calls so that you get a few big packets instead of many
small ones.  Since XSync waits for the server to process all
commands, it is slower than XFlush, but sometimes it is necessary
to do this.

It gets even more complicated because a lot of X...() calls (e.g.
all XGet... and XQuery... functions) automatically flush the so
called request buffer.  Reducing the number of such calls is
another goal for optimisation.  Unfortunately I could never find a
complete list of the X functions that flush the request buffer.

> but I wouldn't call them evil!

Okay, I sometimes put code in macros too, but *only* if it is a
single command like

#define SET_USER_STATES(fw, mask) (fw)->flags.user_states |= (mask)

Longer macros almost always lead to tears at some point in the
future.  Sure, functions are inefficient compared with macros in
terms of speed, but with that reasoning you'd have to put the
whole program in the main function.  I bet you could even make it
smaller with the 'proper' use of gotos ;-)

Bye

Dominik ^_^  ^_^

---

From: Dave Trollope <[email-masked]>
Date: Mon, 25 Mar 2002 00:06:06 -0600

Hi

I include a patch file for some of the things discussed below. I noticed a couple
have been changed in the past few days as it is.

Dave

> but I wouldn't call them evil!
? origexes
? alloc.pch
Index: fvwm/add_window.c
===================================================================
RCS file: /home/cvs/fvwm/fvwm/fvwm/add_window.c,v
retrieving revision 1.282
diff -u -u -r1.282 add_window.c
--- fvwm/add_window.c	2002/03/25 00:09:35	1.282
+++ fvwm/add_window.c	2002/03/25 06:10:10
@@ -376,8 +376,6 @@
 	FvwmWindow save_state;
 	FvwmWindow *savewin = NULL;
 
-	memset(&save_state, '\0', sizeof(FvwmWindow));
-
 	/*
 	  Allocate space for the FvwmWindow struct, or reuse an
 	  old one (on Recapture).
@@ -385,10 +383,6 @@
 	if (ReuseWin == NULL)
 	{
 		*pfw = (FvwmWindow *)safemalloc(sizeof(FvwmWindow));
-		if (*pfw == (FvwmWindow *)0)
-		{
-			return False;
-		}
 	}
 	else
 	{
Index: fvwm/menustyle.c
===================================================================
RCS file: /home/cvs/fvwm/fvwm/fvwm/menustyle.c,v
retrieving revision 1.2
diff -u -u -r1.2 menustyle.c
--- fvwm/menustyle.c	2002/03/23 11:59:59	1.2
+++ fvwm/menustyle.c	2002/03/25 06:10:15
@@ -270,7 +270,7 @@
 	}
 	else
 	{
-		buffer = (char *)safemalloc(strlen(action) + 100);
+		buffer = (char *)alloca(strlen(action) + 100);
 		sprintf(buffer,
 			"* \"%s\", Foreground \"%s\", Background \"%s\", "
 			"Greyed \"%s\", Font \"%s\", \"%s\"",
@@ -279,7 +279,6 @@
 			"Animation" : "AnimationOff");
 		action = buffer;
 		menustyle_parse_style(F_PASS_ARGS);
-		free(buffer);
 	}
 
 	if (fore)
Index: libs/Graphics.c
===================================================================
RCS file: /home/cvs/fvwm/fvwm/libs/Graphics.c,v
retrieving revision 1.55
diff -u -u -r1.55 Graphics.c
--- libs/Graphics.c	2002/03/23 01:18:15	1.55
+++ libs/Graphics.c	2002/03/25 06:10:19
@@ -72,7 +72,7 @@
 		}
 		return;
 	}
-	seg = (XSegment*)safemalloc(sizeof(XSegment) * line_width);
+	seg = (XSegment*)alloca(sizeof(XSegment) * line_width);
 	/* left side, from 0 to the lesser of line_width & just over half w */
 	for (i = 0; (i < line_width) && (i <= w / 2); i++) {
 		seg[i].x1 = x+i; seg[i].y1 = y+i+a;
@@ -97,7 +97,6 @@
 		seg[i].x2 = x+i+1-a; seg[i].y2 = y+i;
 	}
 	XDrawSegments(dpy, d, ReliefGC, seg, i);
-	free(seg);
 
 	return;
 }
Index: libs/Module.c
===================================================================
RCS file: /home/cvs/fvwm/fvwm/libs/Module.c,v
retrieving revision 1.31
diff -u -u -r1.31 Module.c
--- libs/Module.c	2002/03/04 07:26:00	1.31
+++ libs/Module.c	2002/03/25 06:10:23
@@ -164,14 +164,13 @@
 
   while ( (temp = strchr(hold, ',')) != NULL )
   {
-    char *temp_msg = (char*)safemalloc(temp - hold + 1);
+    char *temp_msg = (char*)alloca(temp - hold + 1);
 
     strncpy(temp_msg, hold, (temp - hold));
     temp_msg[(temp - hold)] = '\0';
     hold = temp + 1;
 
     SendText(fd, temp_msg, window);
-    free(temp_msg);
   } /* while */
 
   /*

---

From: Dominik Vogt <[email-masked]>
Date: Mon, 25 Mar 2002 11:13:27 +0100

> have been changed in the past few days as it is.

Thanks, I have applied the patches.

Bye

Dominik ^_^  ^_^

---

From: Dave Trollope <[email-masked]>
Date: Wed, 27 Mar 2002 19:30:00 -0600

Hi,

Great, I will look at the other things we discussed in a few days when work has calmed
down...

Dave