<div>Hi,</div><div><br></div><div>Thanks for your patch, it works well, the output is the same with what it is before.</div><div>To do further optimization, I try to use more subtle bit operation in encoding, it does make a little progress.</div><div><span style="line-height: 1.5;">The get_optimal_split cost 72% of the time for encoding, but I can hardly apply more optimization to it.</span></div><div><span style="line-height: 1.5;">I will try to optimize the dynamic programming algorithm.</span></div><div><span style="line-height: 1.5;"><br></span></div><div>>>We also recommend using Linux for development work rather than Windows.</div><div><br></div><div>I have a ubuntu installed in my machine, but in ubuntu, my machine cannot awake from hiberating, sleeping....</div><div>I tried many methods but finally failed, so if not necessary, I don't switch to ubuntu.</div><div><br></div><div>Best</div><div>Regards</div><div><br></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> Thu, Mar 13, 2014 06:49 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] Optimized VSEncoding</div></div><div><br></div>On Thu, Mar 13, 2014 at 10:41:02AM +0800, Hurricane Tong wrote:<br>> When only encoding the first 1000lines, <br>> both cost 0ms to decode and VS cost 1ms to encode while Interpolative cost 0ms,<br>> 1000lines is just too little to catch the difference in my test.<br><br>As Richard says, there are better ways to do timing tests than calling<br>a fairly low resolution timer like clock() before and after a single<br>run.<br><br>We also recommend using Linux for development work rather than Windows.<br>That would help here as there are better open source profiling tools<br>available on Linux.<br><br>> I upload the source code to https://github.com/HurricaneTong/Xapian/tree/master/VSEncoder<br><br>Thanks.<br><br>You're inserting repeatedly at the start of vector S - each time you do<br>that the entire current contents of the vector have to be copied up one<br>place to make room, which means that inserting N items has cost O(N*N).<br><br>But vector::push_back() is O(1), so pushing back N items has cost O(N).<br>And we can just flip the loop which uses the items to run backwards<br>through S instead of forwards.<br><br>I've attached a quick patch to show what I mean.  I haven't checked the<br>output is the same as before, so this might not be quite right - the<br>patch is really just to make it clearer what I'm talking about.<br><br>Making this change reduces the encoding time by a factor of about 3.6<br>for me for the linux.postlist case (though if the patch isn't quite<br>right this reduction may not be either).  And that's still ~14 times as<br>long as interpolative coding takes, but I suspect there's further scope<br>for speeding it up.<br><br>Cheers,<br>    Olly<br><br></div>