Mailing-List: contact lucy-dev-help@lucene.apache.org; run by ezmlm
Precedence: bulk
Reply-To: lucy-dev@lucene.apache.org
Received-SPF: pass (athena.apache.org: local policy)
Date: Sat, 27 Sep 2008 14:14:57 -0700
To: lucy-dev@lucene.apache.org
Subject: Re: Posting codecs
Message-ID: <20080927211457.GA22981@rectangular.com>
References: <f31e99f40809131356w402aa18avf97ed6471301123@mail.gmail.com>
 <581D4B54-2ABA-4DEA-AC5A-78417E3348A9@rectangular.com>
 <65d3176c0809142202q39d94a83o985df3c95a7867a5@mail.gmail.com>
 <f31e99f40809171123j39032e94q3966631889634593@mail.gmail.com>
 <65d3176c0809171316s31c65048ue6afcb540d845694@mail.gmail.com>
 <7AFF05A2-FE1E-4A35-B3AE-E111DD10F068@rectangular.com>
 <65d3176c0809191125g3c7fd1fav88a4e7c86f9b41ec@mail.gmail.com>
 <FDBA3210-1DB0-4D26-9B3B-1305D4E2BD56@rectangular.com>
 <65d3176c0809212335l64baebfw5abc259fbc417f8d@mail.gmail.com>
 <65d3176c0809260030t4e600cf5g43d5fef6e6637029@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <65d3176c0809260030t4e600cf5g43d5fef6e6637029@mail.gmail.com>
User-Agent: Mutt/1.5.13 (2006-08-11)
From: Marvin Humphrey <marvin@rectangular.com>


On Sep 26, 2008, at 12:30 AM, Nathan Kurz wrote:

> The first step would be to switch InStream to using mmap() instead of
> its user level buffering.   This looks surprisingly easy, presuming we
> are allowed to ignore Windows' compatibility, or at least Windows'
> performance.

Windows has MapViewOfFile.  If that allows us to duplicate the stuff we can do
with mmap on Unixen, great.  If not, we can fall back to the current
implementation of reading into a malloc'd buffer.

> The second step would then be to expose InStream->buf,  

I'm warming to the idea of exposing the raw buffer.  It's actually a pretty
flexible approach -- better than, say, exposing a FILE*.

I think we'd want InStream to expose two pointers: the current buffer pointer,
and the end of the buffer.  

> probably via an accessor so that EOF can be reported.   

It would be bad to expose InStream->buf directly, thereby freezing the layout
of the InStream struct up to that member, but since we're trying to cut down on
function call overhead, the cost of the accessor is a bit of a bummer.  As an
alternative, we might consider using a static inline functions and a variation
on the inside-out technique we use for method calls.

  extern size_t Kino_InStream_Buf_MEMBER_OFFSET;

  static CHY_INLINE char**
  Kino_InStream_Raw_Buf(kino_InStream *self)
  {
      char *const byteself = (char*)self;
      char *const buf = byteself + Kino_InStream_Buf_MEMBER_OFFSET;
      return &buf;
  }

Since that's a static inline function, there's no function call overhead.  Of
course we can't go back and change the behavior of the function call later like
we could with a traditional accessor, and we're committing to having a real
char* buf member in the InStream struct.  However, we're not committing that
"buf" will be located at a fixed offset within the InStream struct -- only that
there will be a variable named Kino_InStream_Buf_MEMBER_OFFSET which will tell
you where that offset is.  Thus the layout of InStream can stay private.

InStream_Raw_Buf_End() would be implemented nearly the same way, but would
return a char* instead of a char**:

  extern size_t Kino_InStream_Buf_End_MEMBER_OFFSET;
  
  static CHY_INLINE char*
  Kino_InStream_Raw_Buf_End(kino_InStream *self)
  {
      char *const byteself = (char*)self;
      char *const buf_end = byteself + Kino_InStream_Buf_End_MEMBER_OFFSET;
      return buf;
  }

I think we should leave it up to the caller to ensure that InStream->buf never
advances beyond InStream->buf_end and that refill() get called when necessary.

> but once we are using mmap we shouldn't ever need to call refill().  

What if the index is large enough that it we exceed the system's addressable
space?  I think we have to mmap using the system page size.  Which means that
to avoid overruns we'll have to track our position within the file and call
refill() every once in a while.

> There would need to be some implied rules, such as never go beyond the
> current Posting.

We might be able to kick in an optimization if we can determine that the buffer
has bytes left exceeding the maximum length of the current posting format: we'd
branch to code that doesn't do bounds checking and never calls refill.

There's a downside to that, though.  Code that does bounds checking will throw
meaningful exceptions as soon as an overrun occurs.  Code that doesn't do
bounds checking will cause memory errors, with unpredictable consequences.

Also, many posting formats won't have a theoretical maximum length.  The
current implementation of ScorePosting doesn't for instance, because there's no
ceiling on the number of positions.

> The third step is to change ScorePost->read_record to decode the
> VBytes directly from the raw buffer, or perhaps better, to create a
> FastScorePost subclass that does this.  InStream->seek() is  called
> after the buffer is read to update Instream->buf and assert() any
> reads that go to far.

We should ape Lucene and give PostingList a Bulk_Read() method, which gets
called by the TermScorer subclass.

> The nice part about this approach is that we should get a nice
> speed-up for the common use cases while requiring very few API
> changes.  Old scorers et al can still continue as they did before, and
> new ones can change over gradually.
> 
> The downside is that each Scorer remains tied to particular index
> format.  Long-term I still think this is disastrous, but in the short
> term it's not that bad.  

Can you please elaborate on what you see as the downsides?

> But perhaps we can delay solving this problem until you get P4Delta ready to
> go.

The hard part about implementing PForDelta is that it involves block read/write
of integers.  KS isn't set up to do that, either at index-time or search-time.

Whether InStream is refills its buffer using mmap() or read() is a completely
separate problem, though -- so let's get mmap() taken care of first.

Marvin Humphrey
Rectangular Research
http://www.rectangular.com/