Thread: allowing broader use of simplehash
I recently became annoyed while working on patch A that I could not use simplehash in shared memory, and then I became annoyed again while working on patch B that I could not use simplehash in frontend code. So here are a few patches for discussion. A significant problem in either case is that a simplehash wants to live in a memory context; no such thing exists either for data in shared memory nor in frontend code. However, it seems to be quite easy to provide a way for simplehash to be defined so that it doesn't care about memory contexts. See 0001. As far as frontend code goes, the only other problem I found is that it makes use of elog() to signal some internal-ish messages. It seemed to me that the easiest thing to do was, if FRONTEND is defined, use pg_log_error(...) instead of elog(ERROR, ...). For the one instance of elog(LOG, ...) in simplehash.h, I chose to use pg_log_info(). It's not really equivalent, but it's probably the closest thing that currently exists, and I think it's good enough for what's basically a debugging message. See 0002. I think those changes would also be enough to allow simplehash to be used in a dynamic shared area (DSA). Using it in the main shared memory segment seems more problematic, because simplehash relies on being able to resize the hash table. Shared hash tables must have a fixed maximum size, but with dynahash, we can count on being able to use all of the entries without significant performance degradation. simplehash, on the other hand, uses linear probing and relies on being able to grow the hash table as a way of escaping collisions. By default, the load factor is not permitted to drop below 0.1, so to mimic the collision-avoidance behavior that we get in backend-private uses of simplehash, we'd have to overallocate by 10x, which doesn't seem desirable. I'd really like to have an alternative to dynahash, which is awkward to use and probably not particularly fast, but I'm not sure simplehash is it. Maybe what we really need is a third (or nth) hash table implementation. Thoughts? -- Robert Haas EnterpriseDB: http://www.enterprisedb.com The Enterprise PostgreSQL Company
Attachment
Hi, Neat! On 2019-12-10 13:07:02 -0500, Robert Haas wrote: > I recently became annoyed while working on patch A that I could not > use simplehash in shared memory, and then I became annoyed again while > working on patch B that I could not use simplehash in frontend code. > So here are a few patches for discussion. I wanted to use it in frontend code a couple times as well. > A significant problem in either case is that a simplehash wants to > live in a memory context; no such thing exists either for data in > shared memory nor in frontend code. However, it seems to be quite easy > to provide a way for simplehash to be defined so that it doesn't care > about memory contexts. See 0001. I wonder if we shouldn't instead just go for an "implicit" memory context instead. It's a bit ugly to have a growing set of different signatures. > As far as frontend code goes, the only other problem I found is that > it makes use of elog() to signal some internal-ish messages. It seemed > to me that the easiest thing to do was, if FRONTEND is defined, use > pg_log_error(...) instead of elog(ERROR, ...). For the one instance of > elog(LOG, ...) in simplehash.h, I chose to use pg_log_info(). It's not > really equivalent, but it's probably the closest thing that currently > exists, and I think it's good enough for what's basically a debugging > message. See 0002. Yea, I think that's fine. > I think those changes would also be enough to allow simplehash to be > used in a dynamic shared area (DSA). Using it in the main shared > memory segment seems more problematic, because simplehash relies on > being able to resize the hash table. Shared hash tables must have a > fixed maximum size, but with dynahash, we can count on being able to > use all of the entries without significant performance degradation. > simplehash, on the other hand, uses linear probing and relies on being > able to grow the hash table as a way of escaping collisions. By > default, the load factor is not permitted to drop below 0.1, so to > mimic the collision-avoidance behavior that we get in backend-private > uses of simplehash, we'd have to overallocate by 10x, which doesn't > seem desirable. It'd be fine to set SH_GROW_MIN_FILLFACTOR to something higher, for many uses. I've only added that after the fact, because somebody demonstrated a workload with SQL level data that had a *lot* of conflicts with our hash functions. But that shouldn't be a concern for most other uses. > I'd really like to have an alternative to dynahash, which is awkward > to use and probably not particularly fast, but I'm not sure simplehash > is it. Maybe what we really need is a third (or nth) hash table > implementation. I think it depends a bit on what use-cases you'd like to cover? I think there's unfortunately a lot of tradeoffs here that are hard to square: 1) For performance, we want the hashtable code to be specialized for the specific key/value combination. I'm not aware of a way to do that without some code generation thing like simplehash. Being able to use simpler pointer math by having fixed sizes, and avoiding indirect function calls, is important for performance. It's fairly annoying to have to do the song-and-dance for simplehash when it's just a local lookup table or something. 2) For performance, using a chained hashtable turns out to be problematic, if the hashtable will often get big (for small tables the CPU caches makes it ok). It's hard to avoid reallocations (and/or smoother growth) for non-chaining tables however. 3) For lots of one-off uses of hashtables that aren't performance critical, we want a *simple* API. That IMO would mean that key/value end up being separately allocated pointers, and that just a comparator is provided when creating the hashtable. 4) For some hashtables it's important to be very concurrent - but it's considerably harder to do that with an open addressing one. While I don't think it's possible to avoid compromise on all these aspects, I think it'd be a lot more realistic to have one implementation fulfilling most needs (except perhaps the concurrency part) if we didn't have the limitations of C. This kind of thing really is one where e.g. C++ style templates are just extremely hard to beat in C. Greetings, Andres Freund
On Tue, Dec 10, 2019 at 4:59 PM Andres Freund <andres@anarazel.de> wrote: > Neat! Thanks. > > A significant problem in either case is that a simplehash wants to > > live in a memory context; no such thing exists either for data in > > shared memory nor in frontend code. However, it seems to be quite easy > > to provide a way for simplehash to be defined so that it doesn't care > > about memory contexts. See 0001. > > I wonder if we shouldn't instead just go for an "implicit" memory > context instead. It's a bit ugly to have a growing set of different > signatures. I don't really know what you mean by this. I don't actually think the different signatures are a big deal. It affects a pretty limited number of functions, and that seems less ugly than trying to create some sort of dummy not-really-a-context object that can live in frontend code, and a lot easier than actually making contexts work in frontend code. The latter might be the better long-term solution, but I don't think we should insist on doing it first. Another way forward would be to replace the MemoryContext references with a void * that happens, in the case of the backend, to be a MemoryContext, and could be NULL when none is required. However, that would give up some type-checking for no current benefit. If simplehash becomes more widely used and at some point it's clear that this would be a net win, we can change it then. -- Robert Haas EnterpriseDB: http://www.enterprisedb.com The Enterprise PostgreSQL Company
On Tue, Dec 10, 2019 at 4:59 PM Andres Freund <andres@anarazel.de> wrote: > 3) For lots of one-off uses of hashtables that aren't performance > critical, we want a *simple* API. That IMO would mean that key/value > end up being separately allocated pointers, and that just a > comparator is provided when creating the hashtable. I think the simplicity of the API is a key point. Some things that are bothersome about dynahash: - It knows about memory contexts and insists on having its own. - You can't just use a hash table in shared memory; you have to "attach" to it first and have an object in backend-private memory. - The usual way of getting a shared hash table is ShmemInitHash(), but that means that the hash table has its own named chunk and that it's in the main shared memory segment. If you want to put it inside another chunk or put it in DSM or whatever, it doesn't work. - It knows about LWLocks and if it's a shared table it needs its own tranche of them. - hash_search() is hard to wrap your head around. One thing I dislike about simplehash is that the #define-based interface is somewhat hard to use. It's not that it's a bad design. It's just you have to sit down and think for a while to figure out which things you need to #define in order to get it to do what you want. I'm not sure that's something that can or needs to be fixed, but it's something to consider. Even dynahash, as annoying as it is, is in some ways easier to get up and running. Probably the two most common uses cases are: (1) a fixed-sized shared memory hash table of fixed-size entries where the key is the first N bytes of the entry and it never grows, or (2) a backend-private or perhaps frontend hash table of fixed-size entries where the key is the first N bytes of the entry, and it grows without limit. I think should consider having specialized APIs for those two cases and then more general APIs that you can use when that's not enough. -- Robert Haas EnterpriseDB: http://www.enterprisedb.com The Enterprise PostgreSQL Company
Hi, On 2019-12-11 10:05:00 -0500, Robert Haas wrote: > On Tue, Dec 10, 2019 at 4:59 PM Andres Freund <andres@anarazel.de> wrote: > > > A significant problem in either case is that a simplehash wants to > > > live in a memory context; no such thing exists either for data in > > > shared memory nor in frontend code. However, it seems to be quite easy > > > to provide a way for simplehash to be defined so that it doesn't care > > > about memory contexts. See 0001. > > > > I wonder if we shouldn't instead just go for an "implicit" memory > > context instead. It's a bit ugly to have a growing set of different > > signatures. > > I don't really know what you mean by this. I don't actually think the > different signatures are a big deal. It affects a pretty limited > number of functions, and that seems less ugly than trying to create > some sort of dummy not-really-a-context object that can live in > frontend code, and a lot easier than actually making contexts work in > frontend code. The latter might be the better long-term solution, but > I don't think we should insist on doing it first. I was basically just thinking that we could pass the context to use via CurrentMemoryContext, instead of explicitly passing it in. > Another way forward would be to replace the MemoryContext references > with a void * that happens, in the case of the backend, to be a > MemoryContext, and could be NULL when none is required. However, that > would give up some type-checking for no current benefit. If simplehash > becomes more widely used and at some point it's clear that this would > be a net win, we can change it then. Yea, that seems worse. I'd rather work on the MemoryContext infrastructure being available for frontend code. Greetings, Andres Freund
Hi,
On 2019-12-11 10:50:16 -0500, Robert Haas wrote:
> On Tue, Dec 10, 2019 at 4:59 PM Andres Freund <andres@anarazel.de> wrote:
> > 3) For lots of one-off uses of hashtables that aren't performance
> > critical, we want a *simple* API. That IMO would mean that key/value
> > end up being separately allocated pointers, and that just a
> > comparator is provided when creating the hashtable.
>
> I think the simplicity of the API is a key point. Some things that are
> bothersome about dynahash:
>
> - It knows about memory contexts and insists on having its own.
Which is a waste, in a good number of cases.
> - You can't just use a hash table in shared memory; you have to
> "attach" to it first and have an object in backend-private memory.
I'm not quite sure there's all that good an alternative to this,
tbh. For efficiency it's useful to have backend-local state, I
think. And I don't really see how to have that without needing to attach.
> - The usual way of getting a shared hash table is ShmemInitHash(), but
> that means that the hash table has its own named chunk and that it's
> in the main shared memory segment. If you want to put it inside
> another chunk or put it in DSM or whatever, it doesn't work.
I don't think it's quite realistic for the same implementation - although
the code could partially be shared and just specialized for both cases -
to be used for DSM and "normal" shared memory. That's however not an
excuse to have drastically different interfaces for both.
> - It knows about LWLocks and if it's a shared table it needs its own
> tranche of them.
> - hash_search() is hard to wrap your head around.
>
> One thing I dislike about simplehash is that the #define-based
> interface is somewhat hard to use. It's not that it's a bad design.
I agree. It's the best I could come up taking the limitations of C into
account, when focusing on speed and type safety. I really think this
type of hack is a stopgap measure, and we ought to upgrade to a subset
of C++.
> It's just you have to sit down and think for a while to figure out
> which things you need to #define in order to get it to do what you
> want. I'm not sure that's something that can or needs to be fixed, but
> it's something to consider. Even dynahash, as annoying as it is, is in
> some ways easier to get up and running.
I have been wondering about providing one simplehash wrapper in a
central place that uses simplehash to store a {key*, value*}, and has a
creation interface that just accepts a comparator. Plus a few wrapper
creation functions for specific types (e.g. string, oid, int64). While
we'd not want to use that for really performance critical paths, for 80%
of the cases it'd be sufficient.
Greetings,
Andres Freund
On Thu, Dec 12, 2019 at 2:33 PM Andres Freund <andres@anarazel.de> wrote: > I was basically just thinking that we could pass the context to use via > CurrentMemoryContext, instead of explicitly passing it in. I thought about that, but as a general rule, replacing a function parameter with a global variable is the wrong direction. One could argue this particular case is a counterexample, and I won't fight tooth and nail if you want to take that position, but I don't think I believe it myself. -- Robert Haas EnterpriseDB: http://www.enterprisedb.com The Enterprise PostgreSQL Company
On Sat, Dec 14, 2019 at 10:24 PM Robert Haas <robertmhaas@gmail.com> wrote: > On Thu, Dec 12, 2019 at 2:33 PM Andres Freund <andres@anarazel.de> wrote: > > I was basically just thinking that we could pass the context to use via > > CurrentMemoryContext, instead of explicitly passing it in. > > I thought about that, but as a general rule, replacing a function > parameter with a global variable is the wrong direction. One could > argue this particular case is a counterexample, and I won't fight > tooth and nail if you want to take that position, but I don't think I > believe it myself. After confirming with Andres that he didn't have an objection to me pressing forward with these patches, I have committed them. -- Robert Haas EnterpriseDB: http://www.enterprisedb.com The Enterprise PostgreSQL Company