From: Greg Smith on
Markus Wanner wrote:
> On 07/20/2010 09:05 PM, Alvaro Herrera wrote:
>> Hmm, deriving code from a paper published by IBM sounds like bad news --
>> who knows what patents they hold on the techniques there?
>
> Yeah, that might be an issue. Note, however, that the lock-based
> variant differs substantially from what's been published. And I sort
> of doubt their patents covers a lot of stuff that's not lock-free-ish.

There's a fairly good mapping of what techniques are patented and which
were only mentioned in research in the Sun dynamic memory patent at
http://www.freepatentsonline.com/7328316.html ; that mentions an earlier
paper by the author of the technique Markus is using, but this was from
before that one was written. It looks like Sun has a large portion of
the patent portfolio in this area, which is particularly troublesome now.

--
Greg Smith 2ndQuadrant US Baltimore, MD
PostgreSQL Training, Services and Support
greg(a)2ndQuadrant.com www.2ndQuadrant.us


--
Sent via pgsql-hackers mailing list (pgsql-hackers(a)postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

From: Markus Wanner on
Greg,

On 07/22/2010 03:59 PM, Greg Smith wrote:
> There's a fairly good mapping of what techniques are patented and which
> were only mentioned in research in the Sun dynamic memory patent at
> http://www.freepatentsonline.com/7328316.html ; that mentions an earlier
> paper by the author of the technique Markus is using, but this was from
> before that one was written. It looks like Sun has a large portion of
> the patent portfolio in this area, which is particularly troublesome now.

Thanks for the pointer, very helpful.

Anybody ever checked jemalloc, or any other OSS allocator out there
against these patents?

Remembering similar patent-discussions, it might be better to not bother
too much and just go with something widely used, based on the assumption
that such a thing is going to enjoy broad support in case of an attack
from a patent troll.

What do you think? What'd be your favorite allocator?

Regards

Markus Wanner

--
Sent via pgsql-hackers mailing list (pgsql-hackers(a)postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

From: Alvaro Herrera on
Excerpts from Markus Wanner's message of jue jul 22 08:49:29 -0400 2010:

> Of course, as mentioned in the bgworker patch, this could be done
> differently. Using solely shared memory, or maybe SLRU to store change
> sets. However, I certainly like the abstraction and guarantees such a
> message passing system provides. It makes things easier to reason about,
> IMO.

FWIW I don't think you should be thinking in "replacing imessages with
SLRU". I rather think you should be thinking in how can you implement
the imessages API on top of SLRU. So as far as the coordinator and
background worker are concerned, there wouldn't be any difference --
they keep using the same API they are using today.

Also let me repeat my earlier comment about imessages being more similar
to multixact than to notify. The content of each multixact entry is
just an arbitrary amount of bytes. If imessages are numbered from a
monotonically increasing sequence, it should be possible to use a very
similar technique, and perhaps you should be able to reduce locking
requirements as well (write messages with only a shared lock, after
you've determined and reserved the area you're going to write).

--
Sent via pgsql-hackers mailing list (pgsql-hackers(a)postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

From: Markus Wanner on
Hi,

On 07/22/2010 08:31 PM, Alvaro Herrera wrote:
> FWIW I don't think you should be thinking in "replacing imessages with
> SLRU". I rather think you should be thinking in how can you implement
> the imessages API on top of SLRU.

Well, I'm rather comparing SLRU with the dynamic allocator. So far I'm
unconvinced that SLRU would be a better base for imessages than a
dynamic allocator. (And I'm arguing that SLRU should use a dynamic
allocator underneath).

> So as far as the coordinator and
> background worker are concerned, there wouldn't be any difference --
> they keep using the same API they are using today.

Agreed, the imessages API to the upper layer doesn't need to care about
the underlying stuff.

> Also let me repeat my earlier comment about imessages being more similar
> to multixact than to notify. The content of each multixact entry is
> just an arbitrary amount of bytes. If imessages are numbered from a
> monotonically increasing sequence,

Well, there's absolutely no need to serialize imessages. So they don't
currently carry any such number. And opposed to multixact entries, they
are clearly directed at exactly one single consumer. Every consumer has
its own receive queue. Sending messages concurrently to different
recipients may happen completely parallelized, without any (b)locking in
between.

The dynamic allocator is the only part of the chain which might need to
do some locking to protect the shared resource (memory) against
concurrent access. Note, however, that wamalloc (as any modern dynamic
allocator) is parallelized to some extent, i.e. concurrent malloc/free
calls don't necessarily need to block each other.

> it should be possible to use a very
> similar technique, and perhaps you should be able to reduce locking
> requirements as well (write messages with only a shared lock, after
> you've determined and reserved the area you're going to write).

Writing to the message is currently (i.e. imessages-on-dynshmem) done
without *any* kind of lock held. So that would rather increase locking
requirements and lower parallelism, I fear.

Regards

Markus

--
Sent via pgsql-hackers mailing list (pgsql-hackers(a)postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

From: Robert Haas on
On Thu, Jul 22, 2010 at 3:09 PM, Markus Wanner <markus(a)bluegap.ch> wrote:
>> FWIW I don't think you should be thinking in "replacing imessages with
>> SLRU". �I rather think you should be thinking in how can you implement
>> the imessages API on top of SLRU.
>
> Well, I'm rather comparing SLRU with the dynamic allocator. So far I'm
> unconvinced that SLRU would be a better base for imessages than a dynamic
> allocator. (And I'm arguing that SLRU should use a dynamic allocator
> underneath).

Here's another idea. Instead of making imessages use an SLRU, how
about having it steal pages from shared_buffers? This would require
segmenting messages into small enough chunks that they'd fit, but the
nice part is that it would avoid the need to have a completely
separate shared memory arena. Ideally, we'd make the infrastructure
general enough that things like SLRU could use it also; and get rid of
or reduce in size some of the special-purpose chunks we're now
allocating.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise Postgres Company

--
Sent via pgsql-hackers mailing list (pgsql-hackers(a)postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers