Recently I have spent time with Skolelinux Drift AS on speeding up a Debian Edu / Skolelinux Lenny installation using LTSP diskless workstations, and in the process I discovered something very surprising. The reason the KDE menu was responding slow when using it for the first time, was mostly due to the way KDE find application icons. I discovered that showing the Multimedia menu would cause more than 20 000 IP packages to be passed between the LTSP client and the NFS server. Most of these were NFS LOOKUP calls, resulting in a NFS3ERR_NOENT response. Because the ping times between the client and the server were in the range 2-20 ms, the menus would be very slow. Looking at the strace of kicker in Lenny (or plasma-desktop i Squeeze - same problem there), I see that the source of these NFS calls are access(2) system calls for non-existing files. KDE can do hundreds of access(2) calls to find one icon file. In my example, just finding the mplayer icon required around 230 access(2) calls.
The KDE code seem to search for icons using a list of icon directories, and the list of possible directories is large. In (almost) each directory, it look for files ending in .png, .svgz, .svg and .xpm. The result is a very slow KDE menu when /usr/ is NFS mounted. Showing a single sub menu may result in thousands of NFS requests. I am not the first one to discover this. I found a KDE bug report from 2009 about this problem, and it is still unsolved.
My solution to speed up the KDE menu was to create a package kde-icon-cache that upon installation will look at all .desktop files used to generate the KDE menu, find their icons, search the icon paths for the file that KDE will end up finding at run time, and copying the icon file to /var/lib/kde-icon-cache/. Finally, I add symlinks to these icon files in one of the first directories where KDE will look for them. This cut down the number of file accesses required to find one icon from several hundred to less than 5, and make the KDE menu almost instantaneous. I'm not quite sure where to make the package publicly available, so for now it is only available on request.
The bug report mention that this do not only affect the KDE menu and icon handling, but also the login process. Not quite sure how to speed up that part without replacing NFS with for example NBD, and that is not really an option at the moment.
If you got feedback on this issue, please let us know on debian-edu (at) lists.debian.org.
Update 2015-08-04: The source of the scripts and associated Debian package is available from the Debian Edu github repository.