| Date: | December 20, 2004 / year-entry #429 |
| Tags: | history |
| Orig Link: | https://blogs.msdn.microsoft.com/oldnewthing/20041220-00/?p=36943 |
| Comments: | 15 |
| Summary: | Nowadays, a major barrier to performance for many classes of programs is paging. We saw earlier this year that paging can kill a server. Today, another example of how performance became tied to paging. The principle is "Don't save anything you can recalculate." This of course, seems counterintuitive: Shouldn't you save the answer so you... |
Nowadays, a major barrier to performance for many classes of programs is paging. We saw earlier this year that paging can kill a server. Today, another example of how performance became tied to paging. The principle is "Don't save anything you can recalculate." This of course, seems counterintuitive: Shouldn't you save the answer so you don't have to recalculate it? The answer is, "It depends." If recalculating the answer isn't very expensive and has good data locality, then you may be better off recalculating it than saving it, especially if saving it reduces locality. For example, if the result is stored in a separate object, you now have to touch a second object—risking a page fault—to get the saved answer. Last time, we saw how Windows 95 applied this principle so that rebasing a DLL didn't thrash your machine. I'm told that the Access team used this principle to reap significant performance gains. Instead of caching results, they just threw them away and recalculated them the next time they were needed. Whether this technique works for you is hard to predict. If your program is processor-bound, then caching computations is probably a good idea. But if your program is memory-bound, then you may be better off getting rid of the cache, since the cache is just creating more memory pressure. |
Comments (15)
Comments are closed. |
I’ll second this. Whenever optimizing, most of the time I’ll prefer saving space over saving time so I rarely ever cache things unless it significantly makes it faster. A lot of the algorithms I use will be (theoretically) orders of magnitude slower but I wont need additonal storage for it. It’s also a win in general because whenever you cache things, there are more "out of resource" conditions you will have to handle and there are more dependencies between variables that gets to be a bigger PITA as more code is introduced over time.
But not always. Don’t forget instruction cache. If re-calculating involves many instructions, it may mean more code page swapping. And also if large look-up tables are involved.
Another thing to consider is… security!
Recalculating things is A Bad Thing if there is a chance that the answer has changed inbetween the two calculations. For example (obviously silly code):
buff = malloc(ComputeTheSize())
// do stuff
memcpy(buff, stuff, ComputeTheSize())
What if another thread did something that makes ComputeTheSize return a different (larger) value between these two lines of code?You have a buffer overrun!
Even using the more secure memcpy_s function won’t help you here.
I think it’s safe to say that saving stuff on the stack (i.e. local variables) is reasonably cost-free unless done to great excess.
This advise applies much more realistically to things like cache tables that are stored on the heap.
So the "security" consideration is more limited. And it has to be traded off against the security problems of storing the computed information, which can be considerable.
How do you profile your code to find chunks of it that page fault a lot? What software profilers do that kind of stuff for you? How do you keep typical applications, web browsers as an example, from page faulting their code and/or data a lot? Why does McAfee virus scan have 2.5 million page faults after using 13 minutes of CPU time? Maybe you can’t answer the last one, but I swear that damn program sucks my computer into 1992. I hate it.
12/20/2004 9:58 AM Peter Torr
> Recalculating things is A Bad Thing if there
> is a chance that the answer has changed
> inbetween the two calculations.
> buff = malloc(ComputeTheSize())
> memcpy(buff, stuff, ComputeTheSize())
> What if another thread did something that
> makes ComputeTheSize return a different
> (larger) value
Good point. But yes indeed, what if another thread did something like that? If you cache the size, and if the new correct size is smaller because the other thread has realloc’ed the thing with a smaller size, then don’t you still encounter the exact same bug?
> Even using the more secure memcpy_s function
> won’t help you here.
Sorry I haven’t read it. Is memcpy_s aware of the actual size of the malloc’ed memory? If so, is there a reason why it would protect against moving too much after another thread shrank the allocated memory, while not protecting against moving too much because the program tried to move an increased size when the actual size didn’t increase?
Ryan Phelps: I don’t know the answer but I could offer a guess.
They might map the file into the process’s address space instead of reading it. They’d have to fault in the all the pages of the file they touch.
Even if they do read it, they probably bring the whole thing into memory at once as a contiguous block. If, for example, they did an alloc / free for each file they read, it could lead to a bunch of paging.
memcpy_s is new for VS 2005 and it requires you to pass a size for both the source and destination buffers.
In keeping with the spirit, I am actually retyping this message each time someone loads this page.
Well, you must have had very quick fingers and very short memory in order to make it efficient (as opposed to not doing it). Just kidding…
Some of us are trained to not use global variables. That’s THE reason not to store it. Paging is irrelevent. I have no objection to storing it in a local variable, which then makes it a decision between
a=something()
DoSomething(A).
DoSomethingElse(A)
or
DoSomething(Something())
DoSomethingElse(Something())
Which I prefer the first (for debugging purposes) but tend to do the second from lazyness. Then of course if there is a problem I then need to rewrite it out as #1.
Thankfully there is a registry so one can avoid global variables while still having them.
If speed becomes an issue I revert to global variables. Normally I pass variables as parameters.
What is interesting is how Windows stores it’s settings. Most are kept in memory but there are a few that are constantly reread fron the registry (many times a second).
David Candy and Peter Torr, I think your examples are not in place. They are good for article on synchronization but not for this one. In multithreaded environment you might want to use synchronization primitives to access resources shared between threads. Peter, memcpy_s is an ill solution, because the root cause of your security hole is the lack of synchronization.
It saves the bits covered by a window. The real question is why.
PingBack from http://www.nynaeve.net/?p=104