<div><br></div><div>Hi,</div><div><br></div><div>The extra space needed for skiplist isn't much.</div><div>I just insert a few triples (-1,x,x) into original chunk.</div><div>The height of the skiplist is no more than 4 currently, so the number of triples won't be very larger.</div><div>And by skiplist, we can apply more compact way to encoding number, such as gamma encoding, </div><div>to replace current way in pack_uint.</div><div>But maybe compactness in doclen post list isn't of much importance, </div><div>after all we only have one doclen post list.</div><div>But if we apply this format to oridinary post list, it may be meaningful. </div><div><br></div><div>As for the case where docids are contiguous, fixed-width format is truly faster, </div><div>but when a docid is deleted, docids aren't contiguous. </div><div>The original contiguous docids become two parts, in each parts, they are contiguous.</div><div>So I think we should first encode the <docid,doclen> in current way, </div><div>when we discover some contiguous id block, then we use fixed-width,</div><div>and after the contiguous block is encoded, we then turn back to current way. </div><div><br></div><div>Best Regards</div><div><br></div><div><div style="color:#909090;font-family:Arial Narrow;font-size:12px">------------------</div><div style="font-size:14px;font-family:Verdana;color:#000;">Shangtong Zhang,<div>Second Year Undergraduate,</div><div>School of Computer Science,</div><div>Fudan University, China.</div></div></div><div> </div><div><div><br></div><div><br></div><div style="font-size: 12px;font-family: Arial Narrow;padding:2px 0 2px 0;">------------------ Original ------------------</div><div style="font-size: 12px;background:#efefef;padding:8px;"><div><b>From: </b> "Olly Betts";<olly@survex.com>;</div><div><b>Date: </b> Sun, May 11, 2014 03:12 PM</div><div><b>To: </b> "Hurricane Tong"<zhangshangtong.cpp@qq.com>; <wbr></div><div><b>Cc: </b> "xapian-devel"<xapian-devel@lists.xapian.org>; <wbr></div><div><b>Subject: </b> Re: [Xapian-devel] some trouble when devising skiplist</div></div><div><br></div>On Sat, May 10, 2014 at 11:12:12AM +0800, Hurricane Tong wrote:<br>> I was confronted with some trouble, I describe the trouble in my journal<br>> http://trac.xapian.org/wiki/GSoC2014/Posting%20list%20encoding%20improvements/Journal#May10<br>> And corresponding code is in my git.<br><br>How big is your encoded list + skip list?<br><br>I wonder if a skip list is not worth the complications it causes on<br>update.<br><br>If we optimise for the case of used document ids being mostly contiguous<br>(which is often the case), we could just store a list of the lengths<br>(with a dummy value for any gaps).  If we used a fixed-width format,<br>then looking up a document length is O(1) (it's effectively an array<br>subscripting operation), and that'll definitely be faster than<br>navigating via a skip list.<br><br>And that's also easy to update (the hardest case is when a new document<br>length exceeds the fixed size, and you need to reencode or split).<br><br>E.g. if all the doc lengths in a chunk were < 65536 (which is often<br>going to be true), you would need 2 bytes per document.  The current<br>docid delta + vint encoded document length will need at least 2 bytes<br>per document, plus whatever space the skip list takes up.<br><br>Cheers,<br>    Olly<br>.<br></div>