Re: [sqlite] Soft heap limit enforcement performance
--- [EMAIL PROTECTED] wrote: > Joe Wilson <[EMAIL PROTECTED]> wrote: > > Is this memory pooling going to be compile-time optional? > > > > I find that library-specific memory pools are awkward because each > > library tends to have its own schemes that don't play well with each > > other. If you use pools, then that limits the effectiveness of Hoard > > or Boehm GC in a big application. > > There are no current plans to make this optional, since to do > so would instantly double the number of configurations I need > to support. Keeping malloc/free around as a compile-time option might be worth considering if only to be able to debug with Valgrind at the individual allocation level. Trying to debug programs using memory pools, such as the C++ standard template library can be challenging. Some STL implementations offer a malloc/free allocator as a debug alternative. > We have no plans to go to mmap or sbrk for memory. All of the > memory SQLite will manage will come from either a static array > (mem3.c) or from a few large mallocs (mem1.c and mem2.c). I > fail to see how this could adversely effect other libraries > within the same program. It just means that SQLite calls > malloc less often. When an allocator has an entire program's memory to deal with it might be able to optimize its allocations - either for space or speed. For example: http://www.hoard.org/ "...false sharing in your application: threads on different CPUs can end up with memory in the same cache line, or chunk of memory. Accessing these falsely-shared cache lines is hundreds of times slower than accessing unshared cache lines." __ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com - To unsubscribe, send email to [EMAIL PROTECTED] -
Re: [sqlite] Soft heap limit enforcement performance
--- [EMAIL PROTECTED] wrote: > Joe Wilson <[EMAIL PROTECTED]> wrote: > > --- [EMAIL PROTECTED] wrote: > > > Mostly I am interested in making sure that malloc(1000) does not > > > fail even though you have 5 bytes free and they just happen > > > to be scattered about as 100 discontinguous blocks of 500 bytes > > > each. > > > > It's a good goal. You can reduce the likelihood of failure perhaps, > > but I don't think that you can guarantee it without moving blocks > > and reswivelling all the pointers. > > So Joe's advice is give up and go home. Duely noted. But if it > is all the same to you, I think I will ignore this advice and > press onward... Not sure how you concluded that from what I wrote. I merely suggested that moving blocks of memory may be more effective in not fragmenting memory. You disagree. No problem. __ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com - To unsubscribe, send email to [EMAIL PROTECTED] -
Re: [sqlite] Soft heap limit enforcement performance
At 19:41 30/10/2007, you wrote: Mostly I am interested in making sure that malloc(1000) does not fail even though you have 5 bytes free and they just happen to be scattered about as 100 discontinguous blocks of 500 bytes each. On the embebed device i worked (i made only the micro-os with sqlite) 2 years ago i "designed" a pseudo-handle. This worked with a maximum number of masters (255) and divide the memory pool in 8192 bytes size. Then a byte-map of 64KB (65536 blocks of 8192 bytes) so 64MB of memory pool with 0 for free and any other with the masters owner. Each block can be freed or be owned by any of the 255 masters. Of course it had internal fragmentation and minimal external, but the block size can change to any other value or the byte-map (but then a linear search for free or next blocks) and blocks can be moved for minimize external fragmentation. - To unsubscribe, send email to [EMAIL PROTECTED] -
Re: [sqlite] Soft heap limit enforcement performance
Joe Wilson <[EMAIL PROTECTED]> wrote: > --- [EMAIL PROTECTED] wrote: > > Mostly I am interested in making sure that malloc(1000) does not > > fail even though you have 5 bytes free and they just happen > > to be scattered about as 100 discontinguous blocks of 500 bytes > > each. > > It's a good goal. You can reduce the likelihood of failure perhaps, > but I don't think that you can guarantee it without moving blocks > and reswivelling all the pointers. So Joe's advice is give up and go home. Duely noted. But if it is all the same to you, I think I will ignore this advice and press onward... > > Is this memory pooling going to be compile-time optional? > > I find that library-specific memory pools are awkward because each > library tends to have its own schemes that don't play well with each > other. If you use pools, then that limits the effectiveness of Hoard > or Boehm GC in a big application. > There are no current plans to make this optional, since to do so would instantly double the number of configurations I need to support. We have no plans to go to mmap or sbrk for memory. All of the memory SQLite will manage will come from either a static array (mem3.c) or from a few large mallocs (mem1.c and mem2.c). I fail to see how this could adversely effect other libraries within the same program. It just means that SQLite calls malloc less often. -- D. Richard Hipp <[EMAIL PROTECTED]> - To unsubscribe, send email to [EMAIL PROTECTED] -
Re: [sqlite] Soft heap limit enforcement performance
--- [EMAIL PROTECTED] wrote: > Mostly I am interested in making sure that malloc(1000) does not > fail even though you have 5 bytes free and they just happen > to be scattered about as 100 discontinguous blocks of 500 bytes > each. It's a good goal. You can reduce the likelihood of failure perhaps, but I don't think that you can guarantee it without moving blocks and reswivelling all the pointers. Most of the better mallocs already perform the similar-size block pool optimization. > > Also, I'm not sure how many libc functions sqlite uses at this > > point. But some of them could malloc memory that is beyond the reach > > of your pools. Then there's the application's mallocs to consider > > as well. > > memcpy, memset, strlen. I think that is about the full set. > SQLite does not use libc very much, as that limits its portability > to embedded platforms. There's also the date functions localtime and gettimeofday. Perhaps they don't malloc in most implementations. > > Are you planning to keep allocations from different connections > > from different databases seperate? It would be nice to have > > unrelated databases on different threads not share a common memory > > pool which would help multi-threaded concurrency. > > Partially. My plan is to have a single global memory space that > all threads share. But each thread grabs big hunks of that space > for its own use on (relatively) infrequent occasions - or at least > with less frequency than mallocs currently occur. So the > synchronization overhead, while not zero, is reduced. Anything is better than 'the one big malloc lock' for concurrency. Is this memory pooling going to be compile-time optional? I find that library-specific memory pools are awkward because each library tends to have its own schemes that don't play well with each other. If you use pools, then that limits the effectiveness of Hoard or Boehm GC in a big application. __ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com - To unsubscribe, send email to [EMAIL PROTECTED] -
Re: [sqlite] Soft heap limit enforcement performance
Joe Wilson <[EMAIL PROTECTED]> wrote: > --- [EMAIL PROTECTED] wrote: > > Joe Wilson <[EMAIL PROTECTED]> wrote: > > > The only real way to prevent allocation fragmentation is to move > > > blocks of memory around - > > > > Not true. You can prevent fragmentation, for example, by > > not allocating objects beside each other that will be destroyed > > at different times. Or, you can pick a single allocation size > > and only do mallocs of exactly that size. The latter approach > > is what we are moving towards for SQLite. The allocation size > > would be the size of what Emery calls a "reap". If you deal > > with large strings and blobs you might need to allocate a chunk > > of memory larger than this, which destroys your fragmentation > > guarantees. But at least you can write testable requirements > > about when you guarantee that fragmentation will not occur. > > Maybe the nomenclature is confusing me, but you are not *preventing* > memory fragmentation with your proposed scheme, but limiting its > effects. Mostly I am interested in making sure that malloc(1000) does not fail even though you have 5 bytes free and they just happen to be scattered about as 100 discontinguous blocks of 500 bytes each. > By rounding up memory allocations you will inevitably > still have some unused dead memory areas. It's not fragmentation, > per se, but wasted space nonetheless. Memory lifetime analysis is > great but you have to be very vigilant in your code. > > If you only use small database fields perhaps you can get some sort > of limited memory fragmentation guarantee, but when you have large > blobs and strings that require contiguous memory, as you point out, > all bets are off. Correct. For really large strings and blobs, you can use the new incremental I/O mechanism, though, and still avoid using large contiguous blocks of memory. That is more work for the program, but if you are writing an application where this kind of thing is important, that is what you have to do. > > Also, I'm not sure how many libc functions sqlite uses at this > point. But some of them could malloc memory that is beyond the reach > of your pools. Then there's the application's mallocs to consider > as well. memcpy, memset, strlen. I think that is about the full set. SQLite does not use libc very much, as that limits its portability to embedded platforms. > > But the ultimate test is comparing the total memory arena size > against how many real bytes are allocated and in use. If your > library can increase the percentage of heap used more than a > generic malloc like Lea's, then it will be useful. There is generally a space v. speed tradeoff. Allocators that make more efficient use of memory are slower than those that waste a lot of memory. It is unclear at this point what the best tradeoff will be for SQLite. Probably it will vary from one application to another, suggesting that it should be tunable. > > Are you planning to keep allocations from different connections > from different databases seperate? It would be nice to have > unrelated databases on different threads not share a common memory > pool which would help multi-threaded concurrency. > Partially. My plan is to have a single global memory space that all threads share. But each thread grabs big hunks of that space for its own use on (relatively) infrequent occasions - or at least with less frequency than mallocs currently occur. So the synchronization overhead, while not zero, is reduced. -- D. Richard Hipp <[EMAIL PROTECTED]> - To unsubscribe, send email to [EMAIL PROTECTED] -
Re: [sqlite] Soft heap limit enforcement performance
[EMAIL PROTECTED] wrote: Joe Wilson <[EMAIL PROTECTED]> wrote: The only real way to prevent allocation fragmentation is to move blocks of memory around - Not true. You can prevent fragmentation, for example, by not allocating objects beside each other that will be destroyed at different times. Or, you can pick a single allocation size and only do mallocs of exactly that size. The latter approach is what we are moving towards for SQLite. The allocation size would be the size of what Emery calls a "reap". If you deal with large strings and blobs you might need to allocate a chunk of memory larger than this, which destroys your fragmentation guarantees. But at least you can write testable requirements about when you guarantee that fragmentation will not occur. You are correct that avoiding fragmentation is very difficult. But is also very important for some users and it is thus something we want to be able to provide. -- D. Richard Hipp <[EMAIL PROTECTED]> Great foresight. Programs which should run unattended but fail from time to time by running out of heap are a nuisance. We had some success by allocating memory in fixed size chunks which have optional smaller chunks internally. Fragmentation of the checker board type is avoided at the expense of sub-optimal packing. The large chunk is sized to fit the biggest dynamically allocated object. The chunks are contiguous. On portable software which cannot tolerate fragmentation and has a limited number of dynamically allocated types avoiding free and using a free list for each type is very robust. Lurking problems caused by squirrelly mallocs are avoided. After running for a few months a high water point in memory is established and memory usage does not creep thereafter. - To unsubscribe, send email to [EMAIL PROTECTED] -
Re: [sqlite] Soft heap limit enforcement performance
--- [EMAIL PROTECTED] wrote: > Joe Wilson <[EMAIL PROTECTED]> wrote: > > The only real way to prevent allocation fragmentation is to move > > blocks of memory around - > > Not true. You can prevent fragmentation, for example, by > not allocating objects beside each other that will be destroyed > at different times. Or, you can pick a single allocation size > and only do mallocs of exactly that size. The latter approach > is what we are moving towards for SQLite. The allocation size > would be the size of what Emery calls a "reap". If you deal > with large strings and blobs you might need to allocate a chunk > of memory larger than this, which destroys your fragmentation > guarantees. But at least you can write testable requirements > about when you guarantee that fragmentation will not occur. Maybe the nomenclature is confusing me, but you are not *preventing* memory fragmentation with your proposed scheme, but limiting its effects. By rounding up memory allocations you will inevitably still have some unused dead memory areas. It's not fragmentation, per se, but wasted space nonetheless. Memory lifetime analysis is great but you have to be very vigilant in your code. If you only use small database fields perhaps you can get some sort of limited memory fragmentation guarantee, but when you have large blobs and strings that require contiguous memory, as you point out, all bets are off. Also, I'm not sure how many libc functions sqlite uses at this point. But some of them could malloc memory that is beyond the reach of your pools. Then there's the application's mallocs to consider as well. But the ultimate test is comparing the total memory arena size against how many real bytes are allocated and in use. If your library can increase the percentage of heap used more than a generic malloc like Lea's, then it will be useful. Are you planning to keep allocations from different connections from different databases seperate? It would be nice to have unrelated databases on different threads not share a common memory pool which would help multi-threaded concurrency. __ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com - To unsubscribe, send email to [EMAIL PROTECTED] -
Re: [sqlite] Soft heap limit enforcement performance
Joe Wilson <[EMAIL PROTECTED]> wrote: > The only real way to prevent allocation fragmentation is to move > blocks of memory around - Not true. You can prevent fragmentation, for example, by not allocating objects beside each other that will be destroyed at different times. Or, you can pick a single allocation size and only do mallocs of exactly that size. The latter approach is what we are moving towards for SQLite. The allocation size would be the size of what Emery calls a "reap". If you deal with large strings and blobs you might need to allocate a chunk of memory larger than this, which destroys your fragmentation guarantees. But at least you can write testable requirements about when you guarantee that fragmentation will not occur. You are correct that avoiding fragmentation is very difficult. But is also very important for some users and it is thus something we want to be able to provide. -- D. Richard Hipp <[EMAIL PROTECTED]> - To unsubscribe, send email to [EMAIL PROTECTED] -
Re: [sqlite] Soft heap limit enforcement performance
The only real way to prevent allocation fragmentation is to move blocks of memory around - i.e., return and manilpulate handles to pointers instead of the pointers themselves. But this adds a lot of runtime overhead and is not C friendly. Anything else is just a compromise. Predictive and statistical schemes only go so far. You still get fragmentation. Maybe if you had special logic for moving and compacting the db page cache memory, that might be sufficient. Anyway, it's interesting stuff. I'm curious as to what solution you'll have. --- [EMAIL PROTECTED] wrote: > I have not read it yet, but a quick scan shows that Emery > completely overlooks one of the key reason I am experiementing > with memory pools: provable correctness. General purpose > allocator, such as Doug Lea's, do an excellent job of > preventing and dealing with memory fragmentation. But > they do not (can not) guarantee that memory will never > fragment. We are working on techniques that will guarantee > that the heap will not fragment. And in order to achieve > that, we need very low-level control of the memory allocation. > Hence my recent interest in memory pools. > > There is also quite a bit of interest in this research > from people using SQLite in embedded machines with bad > malloc() implementations (and, I am told, compelling > reasons why they cannot just substitute a better malloc.) > > Emery's observation that memory pools will not magically > cure the performance problems of a legacy application is > quite correct. You cannot just take any old application > that uses malloc, stick memory pools underneath it, and > expect it to work well. Hence, we are also reworking the > upper layers of SQLite to know that they are using memory > pools and to use those pools effectively. > > -- > D. Richard Hipp <[EMAIL PROTECTED]> __ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com - To unsubscribe, send email to [EMAIL PROTECTED] -
Re: [sqlite] Soft heap limit enforcement performance
Joe Wilson <[EMAIL PROTECTED]> wrote: > Hi Richard, > > This might be worth a read. This paper discusses limitations of custom > memory allocators: > > Reconsidering Custom Memory Allocation > http://www.cs.umass.edu/~emery/pubs/berger-oopsla2002.pdf > Interesting paper. Thanks for the link. I have not read it yet, but a quick scan shows that Emery completely overlooks one of the key reason I am experiementing with memory pools: provable correctness. General purpose allocator, such as Doug Lea's, do an excellent job of preventing and dealing with memory fragmentation. But they do not (can not) guarantee that memory will never fragment. We are working on techniques that will guarantee that the heap will not fragment. And in order to achieve that, we need very low-level control of the memory allocation. Hence my recent interest in memory pools. There is also quite a bit of interest in this research from people using SQLite in embedded machines with bad malloc() implementations (and, I am told, compelling reasons why they cannot just substitute a better malloc.) Emery's observation that memory pools will not magically cure the performance problems of a legacy application is quite correct. You cannot just take any old application that uses malloc, stick memory pools underneath it, and expect it to work well. Hence, we are also reworking the upper layers of SQLite to know that they are using memory pools and to use those pools effectively. -- D. Richard Hipp <[EMAIL PROTECTED]> - To unsubscribe, send email to [EMAIL PROTECTED] -
Re: [sqlite] Soft heap limit enforcement performance
Hi Richard, This might be worth a read. This paper discusses limitations of custom memory allocators: Reconsidering Custom Memory Allocation http://www.cs.umass.edu/~emery/pubs/berger-oopsla2002.pdf This post by Emery Berger outlines the problems with Apache Portable Runtime (APR) memory pools specifically: http://apache.slashdot.org/comments.pl?sid=120623=1=0=thread=10160124 Emery Berger's Hoard memory allocator is widely used in multi-threaded programs to improve concurrency. I've used it and the speedups are quite remarkable. In one case, a multi-threaded server throughput was 4X faster on a 8 CPU box - just by changing the malloc implementation to Hoard. Mind you, programs with coarse-grained locks will not see that sort of performance increase. As far as general compactness of memory allocation goes, I've had great success with Doug Lea's malloc implementation. Highly recommended. http://gee.cs.oswego.edu/dl/html/malloc.html http://gee.cs.oswego.edu/pub/misc/malloc.c http://gee.cs.oswego.edu/pub/misc/malloc.h http://g.oswego.edu/ --- [EMAIL PROTECTED] wrote: > We are actively working on the memory management problem in a > fork of the source tree. See > >http://www.sqlite.org/mpool/fossil > > The focus of our current research is in reducing memory fragmentation, > but this is very much related to limiting memory usage. Assuming we > achieve good results, the experimental fork will be folded back into > the CVS tree at some point. __ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com - To unsubscribe, send email to [EMAIL PROTECTED] -
Re: [sqlite] Soft heap limit enforcement performance
patters <[EMAIL PROTECTED]> wrote:
> We rely on the SQLite memory management to enforce the memory usage in our
> application (running on Windows CE). This has worked quite well for us, but
> have found that when we hit the limit, in some circumstances, performance
> drops significantly.
>
> Looking into the internals of SQLite, it seems that when you are at the
> memory limit, an allocation of size N will attempt to free N bytes from the
> pager. We think this should be increased for performance reasons. By
> altering softHeapLimitEnforcer to free more than is necessary, the limit
> isn't reached again (or at least for some time) which helps in our tests,
> though we haven't done a formal benchmark.
>
> Adding these lines to the softHeapLimitEnforcer seem to help:
>
> if (allocSize < inUse/8) {
> allocSize += inUse/8;
> }
>
> Here, the function's being called with an allocSize equal to the page size
> of the database, and inUse is at the soft heap limit. Instead of freeing a
> page (and then being called over and over, essentially), we free 12% of the
> memory in use. If a formal benchmark should be done, this would be the
> figure to tweak -- 12% gives much improved performance in our tests (when
> the heap limit is roughly 1000 pages in size).
>
We are actively working on the memory management problem in a
fork of the source tree. See
http://www.sqlite.org/mpool/fossil
The focus of our current research is in reducing memory fragmentation,
but this is very much related to limiting memory usage. Assuming we
achieve good results, the experimental fork will be folded back into
the CVS tree at some point.
Your idea of releasing more memory that is strictly necessary has
merit. Please note that you can implement such a schema without
making any changes to the SQLite core by registering your own
limiter function using the sqlite3_memory_alarm() interface. Make
a copy of the implementation of softHeapLimitEnforcer() and
sqlite3_soft_heap_limit(), change their names, then adjust
the renamed softHeaplimitEnforcer() to use whatever memory reclaim
policy seems to work best for you.
You are using SQLite 3.5.x, aren't you?
--
D. Richard Hipp <[EMAIL PROTECTED]>
-
To unsubscribe, send email to [EMAIL PROTECTED]
-
