source: nikanabo/current/xdelta/diy/xdelta3-regtest.py@ 185

Last change on this file since 185 was 185, checked in by geyser, 18 years ago
File size: 32.5 KB
Line 
1#!/usr/bin/python2.4
2# xdelta 3 - delta compression tools and library
3# Copyright (C) 2003, 2006, 2007. Joshua P. MacDonald
4#
5# This program is free software; you can redistribute it and/or modify
6# it under the terms of the GNU General Public License as published by
7# the Free Software Foundation; either version 2 of the License, or
8# (at your option) any later version.
9#
10# This program is distributed in the hope that it will be useful,
11# but WITHOUT ANY WARRANTY; without even the implied warranty of
12# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13# GNU General Public License for more details.
14#
15# You should have received a copy of the GNU General Public License
16# along with this program; if not, write to the Free Software
17# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
18
19# TODO: test 1.5 vs. greedy
20
21import os, sys, math, re, time, types, array, random
22import xdelta3main
23import xdelta3
24
25#RCSDIR = '/mnt/polaroid/Polaroid/orbit_linux/home/jmacd/PRCS'
26RCSDIR = '/tmp/PRCS_read_copy'
27SAMPLEDIR = "/tmp/WESNOTH_tmp/diff"
28
29#RCSDIR = 'G:/jmacd/PRCS/prcs/b'
30#SAMPLEDIR = "C:/sample_data/Wesnoth/tar"
31
32#
33MIN_SIZE = 0
34
35TIME_TOO_SHORT = 0.050
36
37SKIP_TRIALS = 2
38MIN_TRIALS = 3
39MAX_TRIALS = 15
40
41SKIP_DECODE = 1
42
43# 10 = fast 1.5 = slow
44MIN_STDDEV_PCT = 1.5
45
46# How many results per round
47MAX_RESULTS = 500
48TEST_ROUNDS = 500
49KEEP_P = (0.5)
50
51# For RCS testing, what percent to select
52FILE_P = (0.30)
53
54# For run-speed tests
55MIN_RUN = 1000 * 1000 * 1
56MAX_RUN = 1000 * 1000 * 10
57
58# Testwide defaults
59ALL_ARGS = [
60 # -v
61 ]
62
63# The first 7 args go to -C
64SOFT_CONFIG_CNT = 7
65
66CONFIG_ORDER = [ 'large_look',
67 'large_step',
68 'small_look',
69 'small_chain',
70 'small_lchain',
71 'max_lazy',
72 'long_enough',
73
74 # > SOFT_CONFIG_CNT
75 'nocompress',
76 'winsize',
77 'srcwinsize',
78 'sprevsz',
79 'iopt',
80 'djw',
81 'altcode',
82 ]
83
84CONFIG_ARGMAP = {
85 'winsize' : '-W',
86 'srcwinsize' : '-B',
87 'sprevsz' : '-P',
88 'iopt' : '-I',
89 'nocompress' : '-N',
90 'djw' : '-Sdjw',
91 'altcode' : '-T',
92 }
93
94def INPUT_SPEC(rand):
95 return {
96
97 # Time/space costs:
98
99 # -C 1,2,3,4,5,6,7
100 'large_look' : lambda d: rand.choice([9]),
101 'large_step' : lambda d: rand.choice([3, 5, 7, 8, 15]),
102 'small_chain' : lambda d: rand.choice([40, 10, 4, 1]),
103 'small_lchain' : lambda d: rand.choice([x for x in [10, 4, 2, 1] if x <= d['small_chain']]),
104 'max_lazy' : lambda d: rand.choice([9, 18, 27, 36, 72, 108]),
105 'long_enough' : lambda d: rand.choice([9, 18, 27, 36, 72, 108]),
106 'small_look' : lambda d: rand.choice([4]),
107
108 # -N
109 'nocompress' : lambda d: rand.choice(['true']),
110
111 # -T
112 'altcode' : lambda d: rand.choice(['false']),
113
114 # -S djw
115 'djw' : lambda d: rand.choice(['false']),
116
117 # Memory costs:
118
119 # -W
120 'winsize' : lambda d: 8 * (1<<20),
121
122 # -B
123 'srcwinsize' : lambda d: 64 * (1<<20),
124
125 # -I 0 is unlimited
126 'iopt' : lambda d: 0,
127
128 # -P only powers of two
129 'sprevsz' : lambda d: rand.choice([x * (1<<16) for x in [4]]),
130 }
131#end
132
133#
134TMPDIR = '/tmp/xd3regtest.%d' % os.getpid()
135
136RUNFILE = os.path.join(TMPDIR, 'run')
137DFILE = os.path.join(TMPDIR, 'output')
138RFILE = os.path.join(TMPDIR, 'recon')
139
140HEAD_STATE = 0
141BAR_STATE = 1
142REV_STATE = 2
143DATE_STATE = 3
144
145#
146IGNORE_FILENAME = re.compile('.*\\.(gif|jpg).*')
147
148# rcs output
149RE_TOTREV = re.compile('total revisions: (\\d+)')
150RE_BAR = re.compile('----------------------------')
151RE_REV = re.compile('revision (.+)')
152RE_DATE = re.compile('date: ([^;]+);.*')
153# xdelta output
154RE_HDRSZ = re.compile('VCDIFF header size: +(\\d+)')
155RE_EXTCOMP = re.compile('XDELTA ext comp.*')
156
157def c2str(c):
158 return ' '.join(['%s' % x for x in c])
159#end
160
161def SumList(l):
162 return reduce(lambda x,y: x+y, l)
163#end
164
165# returns (total, mean, stddev, q2 (median),
166# (q3-q1)/2 ("semi-interquartile range"), max-min (spread))
167class StatList:
168 def __init__(self,l,desc):
169 cnt = len(l)
170 assert(cnt > 1)
171 l.sort()
172 self.cnt = cnt
173 self.l = l
174 self.total = SumList(l)
175 self.mean = self.total / float(self.cnt)
176 self.s = math.sqrt(SumList([(x-self.mean) * (x - self.mean) for x in l]) / float(self.cnt-1))
177 self.q0 = l[0]
178 self.q1 = l[int(self.cnt/4.0+0.5)]
179 self.q2 = l[int(self.cnt/2.0+0.5)]
180 self.q3 = l[min(self.cnt-1,int((3.0*self.cnt)/4.0+0.5))]
181 self.q4 = l[self.cnt-1]+1
182 self.siqr = (self.q3-self.q1)/2.0;
183 self.spread = (self.q4-self.q0)
184 self.str = '%s %d; mean %d; sdev %d; q2 %d; .5(q3-q1) %.1f; spread %d' % \
185 (desc, self.total, self.mean, self.s, self.q2, self.siqr, self.spread)
186 #end
187#end
188
189def RunCommand(args, ok = [0]):
190 #print 'run command %s' % (' '.join(args))
191 p = os.spawnvp(os.P_WAIT, args[0], args)
192 if p not in ok:
193 raise CommandError(args, 'exited %d' % p)
194 #end
195#end
196
197def RunCommandIO(args,infn,outfn):
198 p = os.fork()
199 if p == 0:
200 os.dup2(os.open(infn,os.O_RDONLY),0)
201 os.dup2(os.open(outfn,os.O_CREAT|os.O_TRUNC|os.O_WRONLY),1)
202 os.execvp(args[0], args)
203 else:
204 s = os.waitpid(p,0)
205 o = os.WEXITSTATUS(s[1])
206 if not os.WIFEXITED(s[1]) or o != 0:
207 raise CommandError(args, 'exited %d' % o)
208 #end
209 #end
210#end
211
212class TimedTest:
213 def __init__(self, target, source, runnable,
214 skip_trials = SKIP_TRIALS,
215 min_trials = MIN_TRIALS,
216 max_trials = MAX_TRIALS,
217 min_stddev_pct = MIN_STDDEV_PCT):
218 self.target = target
219 self.source = source
220 self.runnable = runnable
221
222 self.skip_trials = skip_trials
223 self.min_trials = min(min_trials, max_trials)
224 self.max_trials = max_trials
225 self.min_stddev_pct = min_stddev_pct
226
227 self.encode_time = self.DoTest(DFILE,
228 lambda x: x.Encode(self.target, self.source, DFILE))
229 self.encode_size = runnable.EncodeSize(DFILE)
230
231 if SKIP_DECODE:
232 self.decode_time = StatList([1, 1], 'not decoded')
233 return
234 #end
235
236 self.decode_time = self.DoTest(RFILE,
237 lambda x: x.Decode(DFILE, self.source, RFILE),
238 )
239
240 # verify
241 runnable.Verify(self.target, RFILE)
242 #end
243
244 def DoTest(self, fname, func):
245 trials = 0
246 measured = []
247
248 while 1:
249 try:
250 os.remove(fname)
251 except OSError:
252 pass
253
254 start_time = time.time()
255 start_clock = time.clock()
256
257 func(self.runnable)
258
259 total_clock = (time.clock() - start_clock)
260 total_time = (time.time() - start_time)
261
262 elap_time = max(total_time, 0.0000001)
263 elap_clock = max(total_clock, 0.0000001)
264
265 trials = trials + 1
266
267 # skip some of the first trials
268 if trials > self.skip_trials:
269 measured.append((elap_clock, elap_time))
270 #print 'measurement total: %.1f ms' % (total_time * 1000.0)
271
272 # at least so many
273 if trials < (self.skip_trials + self.min_trials):
274 #print 'continue: need more trials: %d' % trials
275 continue
276
277 # compute %variance
278 done = 0
279 if self.skip_trials + self.min_trials <= 2:
280 measured = measured + measured;
281 done = 1
282 #end
283
284 time_stat = StatList([x[1] for x in measured], 'elap time')
285 sp = float(time_stat.s) / float(time_stat.mean)
286
287 # what if MAX_TRIALS is exceeded?
288 too_many = (trials - self.skip_trials) >= self.max_trials
289 good = (100.0 * sp) < self.min_stddev_pct
290 if done or too_many or good:
291 trials = trials - self.skip_trials
292 if not done and not good:
293 #print 'too many trials: %d' % trials
294 pass
295 #clock = StatList([x[0] for x in measured], 'elap clock')
296 return time_stat
297 #end
298 #end
299 #end
300#end
301
302def Decimals(start, end):
303 l = []
304 step = start
305 while 1:
306 r = range(step, step * 10, step)
307 l = l + r
308 if step * 10 >= end:
309 l.append(step * 10)
310 break
311 step = step * 10
312 return l
313#end
314
315# This tests the raw speed of 0-byte inputs
316def RunSpeedTest():
317 for L in Decimals(MIN_RUN, MAX_RUN):
318 SetFileSize(RUNFILE, L)
319
320 trx = TimedTest(RUNFILE, None, Xdelta3Runner(['-W', str(1<<20)]))
321 ReportSpeed(L, trx, '1MB ')
322
323 trx = TimedTest(RUNFILE, None, Xdelta3Runner(['-W', str(1<<19)]))
324 ReportSpeed(L, trx, '512k')
325
326 trx = TimedTest(RUNFILE, None, Xdelta3Runner(['-W', str(1<<18)]))
327 ReportSpeed(L, trx, '256k')
328
329 trm = TimedTest(RUNFILE, None, Xdelta3Mod1(RUNFILE))
330 ReportSpeed(L, trm, 'swig')
331
332 trg = TimedTest(RUNFILE, None, GzipRun1())
333 ReportSpeed(L,trg,'gzip')
334 #end
335#end
336
337def SetFileSize(F,L):
338 fd = os.open(F, os.O_CREAT | os.O_WRONLY)
339 os.ftruncate(fd,L)
340 assert os.fstat(fd).st_size == L
341 os.close(fd)
342#end
343
344def ReportSpeed(L,tr,desc):
345 print '%s run length %u: size %u: time %.3f ms: decode %.3f ms' % \
346 (desc, L,
347 tr.encode_size,
348 tr.encode_time.mean * 1000.0,
349 tr.decode_time.mean * 1000.0)
350#end
351
352class Xdelta3RunClass:
353 def __init__(self, extra):
354 self.extra = extra
355 #end
356
357 def __str__(self):
358 return ' '.join(self.extra)
359 #end
360
361 def New(self):
362 return Xdelta3Runner(self.extra)
363 #end
364#end
365
366class Xdelta3Runner:
367 def __init__(self, extra):
368 self.extra = extra
369 #end
370
371 def Encode(self, target, source, output):
372 args = (ALL_ARGS +
373 self.extra +
374 ['-e'])
375 if source:
376 args.append('-s')
377 args.append(source)
378 #end
379 args = args + [target, output]
380 self.Main(args)
381 #end
382
383 def Decode(self, input, source, output):
384 args = (ALL_ARGS +
385 ['-d'])
386 if source:
387 args.append('-s')
388 args.append(source)
389 #end
390 args = args + [input, output]
391 self.Main(args)
392 #end
393
394 def Verify(self, target, recon):
395 RunCommand(('cmp', target, recon))
396 #end
397
398 def EncodeSize(self, output):
399 return os.stat(output).st_size
400 #end
401
402 def Main(self, args):
403 try:
404 xdelta3main.main(args)
405 except Exception, e:
406 raise CommandError(args, "xdelta3.main exception")
407 #end
408 #end
409#end
410
411class Xdelta3Mod1:
412 def __init__(self, file):
413 self.target_data = open(file, 'r').read()
414 #end
415
416 def Encode(self, ignore1, ignore2, ignore3):
417 r1, encoded = xdelta3.xd3_encode_memory(self.target_data, None, 1000000, 1<<10)
418 if r1 != 0:
419 raise CommandError('memory', 'encode failed: %s' % r1)
420 #end
421 self.encoded = encoded
422 #end
423
424 def Decode(self, ignore1, ignore2, ignore3):
425 r2, data1 = xdelta3.xd3_decode_memory(self.encoded, None, len(self.target_data))
426 if r2 != 0:
427 raise CommandError('memory', 'decode failed: %s' % r1)
428 #end
429 self.decoded = data1
430 #end
431
432 def Verify(self, ignore1, ignore2):
433 if self.target_data != self.decoded:
434 raise CommandError('memory', 'bad decode')
435 #end
436 #end
437
438 def EncodeSize(self, ignore1):
439 return len(self.encoded)
440 #end
441#end
442
443class GzipRun1:
444 def Encode(self, target, source, output):
445 assert source == None
446 RunCommandIO(['gzip', '-cf'], target, output)
447 #end
448
449 def Decode(self, input, source, output):
450 assert source == None
451 RunCommandIO(['gzip', '-dcf'], input, output)
452 #end
453
454 def Verify(self, target, recon):
455 RunCommand(('cmp', target, recon))
456 #end
457
458 def EncodeSize(self, output):
459 return os.stat(output).st_size
460 #end
461#end
462
463class Xdelta1RunClass:
464 def __str__(self):
465 return 'xdelta1'
466 #end
467
468 def New(self):
469 return Xdelta1Runner()
470 #end
471#end
472
473class Xdelta1Runner:
474 def Encode(self, target, source, output):
475 assert source != None
476 args = ['xdelta1', 'delta', '-q', source, target, output]
477 RunCommand(args, [0, 1])
478 #end
479
480 def Decode(self, input, source, output):
481 assert source != None
482 args = ['xdelta1', 'patch', '-q', input, source, output]
483 # Note: for dumb historical reasons, xdelta1 returns 1 or 0
484 RunCommand(args)
485 #end
486
487 def Verify(self, target, recon):
488 RunCommand(('cmp', target, recon))
489 #end
490
491 def EncodeSize(self, output):
492 return os.stat(output).st_size
493 #end
494#end
495
496# exceptions
497class SkipRcsException:
498 def __init__(self,reason):
499 self.reason = reason
500 #end
501#end
502
503class NotEnoughVersions:
504 def __init__(self):
505 pass
506 #end
507#end
508
509class CommandError:
510 def __init__(self,cmd,str):
511 if type(cmd) is types.TupleType or \
512 type(cmd) is types.ListType:
513 cmd = reduce(lambda x,y: '%s %s' % (x,y),cmd)
514 #end
515 print 'command was: ',cmd
516 print 'command failed: ',str
517 print 'have fun debugging'
518 #end
519#end
520
521class RcsVersion:
522 def __init__(self,vstr):
523 self.vstr = vstr
524 #end
525 def __cmp__(self,other):
526 return cmp(self.date, other.date)
527 #end
528 def __str__(self):
529 return str(self.vstr)
530 #end
531#end
532
533class RcsFile:
534
535 def __init__(self, fname):
536 self.fname = fname
537 self.versions = []
538 self.state = HEAD_STATE
539 #end
540
541 def SetTotRev(self,s):
542 self.totrev = int(s)
543 #end
544
545 def Rev(self,s):
546 self.rev = RcsVersion(s)
547 if len(self.versions) >= self.totrev:
548 raise SkipRcsException('too many versions (in log messages)')
549 #end
550 self.versions.append(self.rev)
551 #end
552
553 def Date(self,s):
554 self.rev.date = s
555 #end
556
557 def Match(self, line, state, rx, gp, newstate, f):
558 if state == self.state:
559 m = rx.match(line)
560 if m:
561 if f:
562 f(m.group(gp))
563 #end
564 self.state = newstate
565 return 1
566 #end
567 #end
568 return None
569 #end
570
571 def Sum1Rlog(self):
572 f = os.popen('rlog '+self.fname, "r")
573 l = f.readline()
574 while l:
575 if self.Match(l, HEAD_STATE, RE_TOTREV, 1, BAR_STATE, self.SetTotRev):
576 pass
577 elif self.Match(l, BAR_STATE, RE_BAR, 1, REV_STATE, None):
578 pass
579 elif self.Match(l, REV_STATE, RE_REV, 1, DATE_STATE, self.Rev):
580 pass
581 elif self.Match(l, DATE_STATE, RE_DATE, 1, BAR_STATE, self.Date):
582 pass
583 #end
584 l = f.readline()
585 #end
586 c = f.close()
587 if c != None:
588 raise c
589 #end
590 #end
591
592 def Sum1(self):
593 st = os.stat(self.fname)
594 self.rcssize = st.st_size
595 self.Sum1Rlog()
596 if self.totrev != len(self.versions):
597 raise SkipRcsException('wrong version count')
598 #end
599 self.versions.sort()
600 #end
601
602 def Checkout(self,n):
603 v = self.versions[n]
604 out = open(self.Verf(n), "w")
605 cmd = 'co -ko -p%s %s' % (v.vstr, self.fname)
606 total = 0
607 (inf,
608 stream,
609 err) = os.popen3(cmd, "r")
610 inf.close()
611 buf = stream.read()
612 while buf:
613 total = total + len(buf)
614 out.write(buf)
615 buf = stream.read()
616 #end
617 v.vsize = total
618 estr = ''
619 buf = err.read()
620 while buf:
621 estr = estr + buf
622 buf = err.read()
623 #end
624 if stream.close():
625 raise CommandError(cmd, 'checkout failed: %s\n%s\n%s' % (v.vstr, self.fname, estr))
626 #end
627 out.close()
628 err.close()
629 #end
630
631 def Vdate(self,n):
632 return self.versions[n].date
633 #end
634
635 def Vstr(self,n):
636 return self.versions[n].vstr
637 #end
638
639 def Verf(self,n):
640 return os.path.join(TMPDIR, 'input.%d' % n)
641 #end
642
643 def FilePairsByDate(self, runclass):
644 if self.totrev < 2:
645 raise NotEnoughVersions()
646 #end
647 self.Checkout(0)
648 ntrials = []
649 if self.totrev < 2:
650 return vtrials
651 #end
652 for v in range(0,self.totrev-1):
653 if v > 1:
654 os.remove(self.Verf(v-1))
655 #end
656 self.Checkout(v+1)
657 if os.stat(self.Verf(v)).st_size < MIN_SIZE or \
658 os.stat(self.Verf(v+1)).st_size < MIN_SIZE:
659 continue
660 #end
661
662 result = TimedTest(self.Verf(v+1),
663 self.Verf(v),
664 runclass.New())
665
666 target_size = os.stat(self.Verf(v+1)).st_size
667
668 ntrials.append(result)
669 #end
670
671 os.remove(self.Verf(self.totrev-1))
672 os.remove(self.Verf(self.totrev-2))
673 return ntrials
674 #end
675
676 def AppendVersion(self, f, n):
677 self.Checkout(n)
678 rf = open(self.Verf(n), "r")
679 data = rf.read()
680 f.write(data)
681 rf.close()
682 return len(data)
683 #end
684
685class RcsFinder:
686 def __init__(self):
687 self.subdirs = []
688 self.rcsfiles = []
689 self.others = []
690 self.skipped = []
691 self.biground = 0
692 #end
693
694 def Scan1(self,dir):
695 dents = os.listdir(dir)
696 subdirs = []
697 rcsfiles = []
698 others = []
699 for dent in dents:
700 full = os.path.join(dir, dent)
701 if os.path.isdir(full):
702 subdirs.append(full)
703 elif dent[len(dent)-2:] == ",v":
704 rcsfiles.append(RcsFile(full))
705 else:
706 others.append(full)
707 #end
708 #end
709 self.subdirs = self.subdirs + subdirs
710 self.rcsfiles = self.rcsfiles + rcsfiles
711 self.others = self.others + others
712 return subdirs
713 #end
714
715 def Crawl(self, dir):
716 subdirs = [dir]
717 while subdirs:
718 s1 = self.Scan1(subdirs[0])
719 subdirs = subdirs[1:] + s1
720 #end
721 #end
722
723 def Summarize(self):
724 good = []
725 for rf in self.rcsfiles:
726 try:
727 rf.Sum1()
728 if rf.totrev < 2:
729 raise SkipRcsException('too few versions (< 2)')
730 #end
731 except SkipRcsException, e:
732 #print 'skipping file %s: %s' % (rf.fname, e.reason)
733 self.skipped.append(rf)
734 else:
735 good.append(rf)
736 #end
737 self.rcsfiles = good
738 #end
739
740 def AllPairsByDate(self, runclass):
741 results = []
742 good = []
743 for rf in self.rcsfiles:
744 try:
745 results = results + rf.FilePairsByDate(runclass)
746 except SkipRcsException:
747 print 'file %s has compressed versions: skipping' % (rf.fname)
748 except NotEnoughVersions:
749 print 'testing %s on %s: not enough versions' % (runclass, rf.fname)
750 else:
751 good.append(rf)
752 #end
753 self.rcsfiles = good
754 self.ReportPairs(runclass, results)
755 return results
756 #end
757
758 def ReportPairs(self, name, results):
759 encode_time = 0
760 decode_time = 0
761 encode_size = 0
762 for r in results:
763 encode_time += r.encode_time.mean
764 decode_time += r.decode_time.mean
765 encode_size += r.encode_size
766 #end
767 print '%s rcs: encode %.2f s: decode %.2f s: size %d' % \
768 (name, encode_time, decode_time, encode_size)
769 #end
770
771 def MakeBigFiles(self, rand):
772 f1 = open(TMPDIR + "/big.1", "w")
773 f2 = open(TMPDIR + "/big.2", "w")
774 population = []
775 for file in self.rcsfiles:
776 if len(file.versions) < 2:
777 continue
778 population.append(file)
779 #end
780 f1sz = 0
781 f2sz = 0
782 fcount = int(len(population) * FILE_P)
783 assert fcount > 0
784 for file in rand.sample(population, fcount):
785 m = IGNORE_FILENAME.match(file.fname)
786 if m != None:
787 continue
788 #end
789 r1, r2 = rand.sample(xrange(0, len(file.versions)), 2)
790 f1sz += file.AppendVersion(f1, r1)
791 f2sz += file.AppendVersion(f2, r2)
792 #m.update('%s,%s,%s ' % (file.fname[len(RCSDIR):], file.Vstr(r1), file.Vstr(r2)))
793 #end
794 testkey = 'rcs%d' % self.biground
795 self.biground = self.biground + 1
796
797 print '%s; source %u bytes; target %u bytes' % (testkey, f1sz, f2sz)
798 f1.close()
799 f2.close()
800 return (TMPDIR + "/big.1",
801 TMPDIR + "/big.2",
802 testkey)
803 #end
804
805 def Generator(self):
806 return lambda rand: self.MakeBigFiles(rand)
807 #end
808#end
809
810# find a set of RCS files for testing
811def GetTestRcsFiles():
812 rcsf = RcsFinder()
813 rcsf.Crawl(RCSDIR)
814 if len(rcsf.rcsfiles) == 0:
815 raise CommandError('', 'no RCS files')
816 #end
817 rcsf.Summarize()
818 print "rcsfiles: rcsfiles %d; subdirs %d; others %d; skipped %d" % (len(rcsf.rcsfiles),
819 len(rcsf.subdirs),
820 len(rcsf.others),
821 len(rcsf.skipped))
822 print StatList([x.rcssize for x in rcsf.rcsfiles], "rcssize").str
823 print StatList([x.totrev for x in rcsf.rcsfiles], "totrev").str
824 return rcsf
825#end
826
827class SampleDataTest:
828 def __init__(self, dirs):
829 self.pairs = []
830 while dirs:
831 d = dirs[0]
832 dirs = dirs[1:]
833 l = os.listdir(d)
834 files = []
835 for e in l:
836 p = os.path.join(d, e)
837 if os.path.isdir(p):
838 dirs.append(p)
839 else:
840 files.append(p)
841 #end
842 #end
843 if len(files) > 1:
844 files.sort()
845 for x in xrange(len(files) - 1):
846 self.pairs.append((files[x], files[x+1],
847 '%s-%s' % (files[x], files[x+1])))
848 #end
849 #end
850 #end
851 #end
852
853 def Generator(self):
854 return lambda rand: rand.choice(self.pairs)
855 #end
856#end
857
858# configs are represented as a list of values,
859# program takes a list of strings:
860def ConfigToArgs(config):
861 args = [ '-C',
862 ','.join([str(x) for x in config[0:SOFT_CONFIG_CNT]])]
863 for i in range(SOFT_CONFIG_CNT, len(CONFIG_ORDER)):
864 key = CONFIG_ARGMAP[CONFIG_ORDER[i]]
865 val = config[i]
866 if val == 'true' or val == 'false':
867 if val == 'true':
868 args.append('%s' % key)
869 #end
870 else:
871 args.append('%s=%s' % (key, val))
872 #end
873 #end
874 return args
875#end
876
877#
878class RandomTest:
879 def __init__(self, tnum, tinput, config, syntuple = None):
880 self.mytinput = tinput[2]
881 self.myconfig = config
882 self.tnum = tnum
883
884 if syntuple != None:
885 self.runtime = syntuple[0]
886 self.compsize = syntuple[1]
887 self.decodetime = None
888 else:
889 args = ConfigToArgs(config)
890 result = TimedTest(tinput[1], tinput[0], Xdelta3Runner(args))
891
892 self.runtime = result.encode_time.mean
893 self.compsize = result.encode_size
894 self.decodetime = result.decode_time.mean
895 #end
896
897 self.score = None
898 self.time_pos = None
899 self.size_pos = None
900 self.score_pos = None
901 #end
902
903 def __str__(self):
904 decodestr = ''
905 if not SKIP_DECODE:
906 decodestr = ' %.6f' % self.decodetime
907 #end
908 return 'time %.6f%s size %d%s << %s >>%s' % (
909 self.time(), ((self.time_pos != None) and (" (%s)" % self.time_pos) or ""),
910 self.size(), ((self.size_pos != None) and (" (%s)" % self.size_pos) or ""),
911 c2str(self.config()),
912 decodestr)
913 #end
914
915 def time(self):
916 return self.runtime
917 #end
918
919 def size(self):
920 return self.compsize
921 #end
922
923 def config(self):
924 return self.myconfig
925 #end
926
927 def score(self):
928 return self.score
929 #end
930
931 def tinput(self):
932 return self.mytinput
933 #end
934#end
935
936def PosInAlist(l, e):
937 for i in range(0, len(l)):
938 if l[i][1] == e:
939 return i;
940 #end
941 #end
942 return -1
943#end
944
945# Generates a set of num_results test configurations, given the list of
946# retest-configs.
947def RandomTestConfigs(rand, input_configs, num_results):
948
949 outputs = input_configs[:]
950 have_set = dict([(c,c) for c in input_configs])
951
952 # Compute a random configuration
953 def RandomConfig():
954 config = []
955 cmap = {}
956 for key in CONFIG_ORDER:
957 val = cmap[key] = (INPUT_SPEC(rand)[key])(cmap)
958 config.append(val)
959 #end
960 return tuple(config)
961 #end
962
963 while len(outputs) < num_results:
964 newc = None
965 for i in xrange(10):
966 c = RandomConfig()
967 if have_set.has_key(c):
968 continue
969 #end
970 have_set[c] = c
971 newc = c
972 break
973 if newc is None:
974 print 'stopped looking for configs at %d' % len(outputs)
975 break
976 #end
977 outputs.append(c)
978 #end
979 outputs.sort()
980 return outputs
981#end
982
983def RunTestLoop(rand, generator, rounds):
984 configs = []
985 for rnum in xrange(rounds):
986 configs = RandomTestConfigs(rand, configs, MAX_RESULTS)
987 tinput = generator(rand)
988 tests = []
989 for x in xrange(len(configs)):
990 t = RandomTest(x, tinput, configs[x])
991 print 'Round %d test %d: %s' % (rnum, x, t)
992 tests.append(t)
993 #end
994 results = ScoreTests(tests)
995
996 for r in results:
997 c = r.config()
998 if not test_all_config_results.has_key(c):
999 test_all_config_results[c] = [r]
1000 else:
1001 test_all_config_results[c].append(r)
1002 #end
1003 #end
1004
1005 GraphResults('expt%d' % rnum, results)
1006 GraphSummary('sum%d' % rnum, results)
1007
1008 # re-test some fraction
1009 configs = [r.config() for r in results[0:int(MAX_RESULTS * KEEP_P)]]
1010 #end
1011#end
1012
1013# TODO: cleanup
1014test_all_config_results = {}
1015
1016def ScoreTests(results):
1017 scored = []
1018 timed = []
1019 sized = []
1020
1021 t_min = float(min([test.time() for test in results]))
1022 #t_max = float(max([test.time() for test in results]))
1023 s_min = float(min([test.size() for test in results]))
1024 #s_max = float(max([test.size() for test in results]))
1025
1026 for test in results:
1027
1028 # Hyperbolic function. Smaller scores still better
1029 red = 0.999 # minimum factors for each dimension are 1/1000
1030 test.score = ((test.size() - s_min * red) *
1031 (test.time() - t_min * red))
1032
1033 scored.append((test.score, test))
1034 timed.append((test.time(), test))
1035 sized.append((test.size(), test))
1036 #end
1037
1038 scored.sort()
1039 timed.sort()
1040 sized.sort()
1041
1042 best_by_size = []
1043 best_by_time = []
1044
1045 pos = 0
1046 for (score, test) in scored:
1047 pos += 1
1048 test.score_pos = pos
1049 #end
1050
1051 scored = [x[1] for x in scored]
1052
1053 for test in scored:
1054 test.size_pos = PosInAlist(sized, test)
1055 test.time_pos = PosInAlist(timed, test)
1056 #end
1057
1058 for test in scored:
1059 c = test.config()
1060 s = 0.0
1061 print 'H-Score: %0.9f %s' % (test.score, test)
1062 #end
1063
1064 return scored
1065#end
1066
1067def GraphResults(desc, results):
1068 f = open("data-%s.csv" % desc, "w")
1069 for r in results:
1070 f.write("%0.9f\t%d\t# %s\n" % (r.time(), r.size(), r))
1071 #end
1072 f.close()
1073 os.system("./plot.sh data-%s.csv plot-%s.jpg" % (desc, desc))
1074#end
1075
1076def GraphSummary(desc, results_ignore):
1077 test_population = 0
1078 config_ordered = []
1079
1080 # drops duplicate test/config pairs (TODO: don't retest them)
1081 for config, cresults in test_all_config_results.items():
1082 input_config_map = {}
1083 uniq = []
1084 for test in cresults:
1085 assert test.config() == config
1086 test_population += 1
1087 key = test.tinput()
1088 if not input_config_map.has_key(key):
1089 input_config_map[key] = {}
1090 #end
1091 if input_config_map[key].has_key(config):
1092 print 'skipping repeat test %s vs. %s' % (input_config_map[key][config], test)
1093 continue
1094 #end
1095 input_config_map[key][config] = test
1096 uniq.append(test)
1097 #end
1098 config_ordered.append(uniq)
1099 #end
1100
1101 # sort configs descending by number of tests
1102 config_ordered.sort(lambda x, y: len(y) - len(x))
1103
1104 print 'population %d: %d configs %d results' % \
1105 (test_population,
1106 len(config_ordered),
1107 len(config_ordered[0]))
1108
1109 if config_ordered[0] == 1:
1110 return
1111 #end
1112
1113 # a map from test-key to test-list w/ various configs
1114 input_set = {}
1115 osize = len(config_ordered)
1116
1117 for i in xrange(len(config_ordered)):
1118 config = config_ordered[i][0].config()
1119 config_tests = config_ordered[i]
1120
1121 #print '%s has %d tested inputs' % (config, len(config_tests))
1122
1123 if len(input_set) == 0:
1124 input_set = dict([(t.tinput(), [t]) for t in config_tests])
1125 continue
1126 #end
1127
1128 # a map from test-key to test-list w/ various configs
1129 update_set = {}
1130 for r in config_tests:
1131 t = r.tinput()
1132 if input_set.has_key(t):
1133 update_set[t] = input_set[t] + [r]
1134 else:
1135 #print 'config %s does not have test %s' % (config, t)
1136 pass
1137 #end
1138 #end
1139
1140 if len(update_set) <= 1:
1141 break
1142 #end
1143
1144 input_set = update_set
1145
1146 # continue if there are more w/ the same number of inputs
1147 if i < (len(config_ordered) - 1) and \
1148 len(config_ordered[i + 1]) == len(config_tests):
1149 continue
1150 #end
1151
1152 # synthesize results for multi-test inputs
1153 config_num = None
1154
1155 # map of config to sum(various test-keys)
1156 smap = {}
1157 for (key, tests) in input_set.items():
1158 if config_num == None:
1159 # config_num should be the same in all elements
1160 config_num = len(tests)
1161 smap = dict([(r.config(),
1162 (r.time(),
1163 r.size()))
1164 for r in tests])
1165 else:
1166 # compuate the per-config sum of time/size
1167 assert config_num == len(tests)
1168 smap = dict([(r.config(),
1169 (smap[r.config()][0] + r.time(),
1170 smap[r.config()][1] + r.size()))
1171 for r in tests])
1172 #end
1173 #end
1174
1175 if config_num == 1:
1176 continue
1177 #end
1178
1179 if len(input_set) == osize:
1180 break
1181 #end
1182
1183 summary = '%s-%d' % (desc, len(input_set))
1184 osize = len(input_set)
1185
1186 print 'generate %s w/ %d configs' % (summary, config_num)
1187 syn = [RandomTest(0, (None, None, summary), config,
1188 syntuple = (smap[config][0], smap[config][1]))
1189 for config in smap.keys()]
1190 syn = ScoreTests(syn)
1191 #print 'smap is %s' % (smap,)
1192 #print 'syn is %s' % (' and '.join([str(x) for x in syn]))
1193 GraphResults(summary, syn)
1194 #end
1195#end
1196
1197if __name__ == "__main__":
1198 try:
1199 RunCommand(['rm', '-rf', TMPDIR])
1200 os.mkdir(TMPDIR)
1201
1202 rcsf = GetTestRcsFiles()
1203 generator = rcsf.Generator()
1204
1205 #sample = SampleDataTest([SAMPLEDIR])
1206 #generator = sample.Generator()
1207
1208 rand = random.Random(135135135135135)
1209 RunTestLoop(rand, generator, TEST_ROUNDS)
1210
1211 #RunSpeedTest()
1212
1213 #x3r = rcsf.AllPairsByDate(Xdelta3RunClass(['-9']))
1214 #x3r = rcsf.AllPairsByDate(Xdelta3RunClass(['-9', '-S', 'djw']))
1215 #x3r = rcsf.AllPairsByDate(Xdelta3RunClass(['-9', '-T']))
1216
1217 #x1r = rcsf.AllPairsByDate(Xdelta1RunClass())
1218
1219 except CommandError:
1220 pass
1221 else:
1222 RunCommand(['rm', '-rf', TMPDIR])
1223 pass
1224 #end
1225#end
Note: See TracBrowser for help on using the repository browser.