AMDG On 1/28/2011 10:22 AM, Dean Michael Berris wrote:
On Sat, Jan 29, 2011 at 1:43 AM, Steven Watanabe<watanabesj@gmail.com> wrote:
I'm not sure what this has to do with the OS. The memory manager exists in user space and only goes to the OS when it can't fulfill the request with the memory that it has on hand.
Which OS are we talking about? At least for Linux I know for a fact that the Virtual Memory Manager is an OS-level service. I don't know Windows internals but I'm willing to say that the virtual memory manager exists as an OS-level service. That means the heap that's available to an application would have to be allocated by a VMM before the application even touches the CPU.
There are two layers. The application has a memory manager in the C library which services most requests. This allocator gets more memory from the OS as needed, but usually doesn't release it back to the OS immediately. In ptmalloc2 which is used be glibc, the default settings work something like this: * If the requested size is at least 128 KB use mmap to let the OS handle the request directly. * If there is a block available that's big enough, use it. * try to use sbrk to expand the heap. * If sbrk fails, use mmap to allocate a 1 MB chunk. Note that the OS never gets a mmap request less than 128 KB and all the memory allocated via sbrk is always contiguous.
This means, lets say that you have a memory page that's 4kb long, and you need a contiguous string that is say 9kb, then that means your OS would have to find 3 contiguous memory pages to be able to fit a single string. Say that again, a single string needing 3 *contiguous* memory pages. If this allocation happens on one core and then the process is migrated to a different core for whatever reason that controls a different memory module, then just accessing that string that's even in L3 cache would be a problem.
Humph. 9 KB is not all that much memory. Besides, how often do you have strings this big anyway?
When you're downloading HTML pages and/or building HTML pages, or parsing HTTP requests, it happens a lot. 9kb is a number that's suitable to show that you need multiple contiguous pages for any meaningful discussion on what memory paging effects have something to do with strings and algorithms that deal with strings. Of course this assumes 4kb pages too, the formula would be the same though with just values changing for any platform. ;)
How big are the strings you're really dealing with? 9 KB is just insignificant even in a 32 (31?)-bit virtual address space. As far as I'm concerned, it isn't big until you're talking megabytes, at least. With 64-bit you can exhaust physical memory and use the entire hard drive for swap and still be an order of magnitude short of using up all the virtual address space, even when the hardware restricts you to 48-bit virtual addresses.
But the effect of finding the 5 contiguous pages is what I was trying to highlight. Even if you could grow the original buffers of one of the strings, in a std::string it would still have to be a contiguous chunk of bytes anyway. :)
The page size is simply irrelevant W.R.T. the effect of allocating contiguous memory.
Then all hell breaks loose as your VMM will have to find these 5 pages that sit right next to each other, potentially paging out stuff just so that it can satisfy this simple concatenation request.
In my experience most programs don't come close enough to exhausting their address spaces to make this a big deal. I don't believe that this is as apocalyptic as you're making it out in general.
If we're going to go through "in my experience most programs" I'd say this happens pretty often. ;)
Well, looking at my system right now, the most memory that any process is using is 420 MB. This is still a lot less than the 2 GB limit. The next memory user isn't even close (180 MB) and after that it drops off rapidly. If you're getting this close to running out of address space, contiguous strings are probably the least of your problems anyway. There's no way the 5 contiguous pages make any noticeable difference whatsoever.
You need to be more clear about whether you're talking about physical addresses or virtual addresses. Contiguous pages do not have to be stored in contiguous physical memory.
The fact that contiguous pages don't get stored in contiguous physical memory compounds the problem even more.
Huh?
You feel this a lot when your system starts thrashing and the VMM does the work of swapping pages and re-arranging page tables for you. The round-trips between a CPU page fault and the VMM page fault handler along with potentially invalidating L1/L2/L3 caches costs are significant in environments where you need to get as much things done per second as physically possible. If you can avoid having to go through this dance with a sane memory management strategy, I think that's a win even in the trivial case.
I understand perfectly well that avoiding swapping helps performance. What I still don't understand is how storing a string with contiguous virtual addresses increases the amount of swapping required. Unless you write your own allocator the odds are that splitting up the string into small chunks will spread it across /more/ pages, increasing your working set.
If what you're saying is true than std::deque should be preferable to std::vector, but this is exactly the opposite of what I've always heard.
It depends on what you're trying to do and what algorithms you're applying on your std::dequeue. This is the whole crux of the segmented iterators debate/paper by Matt Austern and others. Segmented versions of the algorithms would make using std::dequeue a lot more preferable if you really needed a data structure that doesn't promote heap fragmentation as much as a growing std::vector does.
I used to like the idea of segmented algorithms. However, I've more recently decided that they just make easy things hard and hard things impossible. The segmented implementation of for_each is bad enough. I don't want even to think about what any algorithm that couldn't easily be implemented in terms of for_each would look like.
string, and the string changes on a process that's working on one processor, the processor has to keep the caches of both up-to-date especially if it's in L1 cache. That means if you're building a string in one thread and simultaneously reading it from another, you're stressing the cache coherence mechanisms used by them multi-core machines.
This sounds like a bad idea to begin with, never mind the performance implications.
Right. Now if you prevented this from even being possible by making a string immutable, I'd say it's a win, no? :)
I disagree. Reading and writing the same data from multiple threads in parallel is a bad idea in general. There's nothing special about strings. If you want to share immutable data, declare it const. Problem solved. No need to force all strings to be immutable just for this.
In fact, I would think that your proposal would make this worse by allowing hidden sharing between apparently unrelated strings.
The hidden sharing will only be a problem if you're allowing mutation. Otherwise it's a good thing from a VMM/Cache perspective all-around (except for the cache line that has a reference count, but that's largely only touched when copies/temporaries get created/destroyed, and in sane systems would be an atomic increment/decrement anyway).
Okay. In Christ, Steven Watanabe