← Back to branch summary

~ubuntu-branches/ubuntu/vivid/golang/vivid

« back to all changes in this revision

Viewing changes to src/pkg/unicode/letter_test.go

  • Committer: Package Import Robot
  • Author(s): James Page
  • Date: 2013-08-20 14:06:23 UTC
  • mfrom: (14.1.23 saucy-proposed)
  • Revision ID: package-import@ubuntu.com-20130820140623-b414jfxi3m0qkmrq
Tags: 2:1.1.2-2ubuntu1
https://launchpad.net/bugs/1211749
https://launchpad.net/bugs/1202027
* Merge from Debian unstable (LP: #1211749, #1202027). Remaining changes:
  - 016-armhf-elf-header.patch: Use correct ELF header for armhf binaries.
  - d/control,control.cross: Update Breaks/Replaces for Ubuntu
    versions to ensure smooth upgrades, regenerate control file.

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/pkg/unicode/letter_test.go
5
5
package unicode_test
6
6
 
7
7
import (
 
8
        "flag"
 
9
        "fmt"
 
10
        "runtime"
 
11
        "sort"
8
12
        "testing"
9
13
        . "unicode"
10
14
)
427
431
                }
428
432
        }
429
433
}
 
434
 
 
435
// Running 'go test -calibrate' runs the calibration to find a plausible
 
436
// cutoff point for linear search of a range list vs. binary search.
 
437
// We create a fake table and then time how long it takes to do a
 
438
// sequence of searches within that table, for all possible inputs
 
439
// relative to the ranges (something before all, in each, between each, after all).
 
440
// This assumes that all possible runes are equally likely.
 
441
// In practice most runes are ASCII so this is a conservative estimate
 
442
// of an effective cutoff value. In practice we could probably set it higher
 
443
// than what this function recommends.
 
444
 
 
445
var calibrate = flag.Bool("calibrate", false, "compute crossover for linear vs. binary search")
 
446
 
 
447
func TestCalibrate(t *testing.T) {
 
448
        if !*calibrate {
 
449
                return
 
450
        }
 
451
 
 
452
        if runtime.GOARCH == "amd64" {
 
453
                fmt.Printf("warning: running calibration on %s\n", runtime.GOARCH)
 
454
        }
 
455
 
 
456
        // Find the point where binary search wins by more than 10%.
 
457
        // The 10% bias gives linear search an edge when they're close,
 
458
        // because on predominantly ASCII inputs linear search is even
 
459
        // better than our benchmarks measure.
 
460
        n := sort.Search(64, func(n int) bool {
 
461
                tab := fakeTable(n)
 
462
                blinear := func(b *testing.B) {
 
463
                        tab := tab
 
464
                        max := n*5 + 20
 
465
                        for i := 0; i < b.N; i++ {
 
466
                                for j := 0; j <= max; j++ {
 
467
                                        linear(tab, uint16(j))
 
468
                                }
 
469
                        }
 
470
                }
 
471
                bbinary := func(b *testing.B) {
 
472
                        tab := tab
 
473
                        max := n*5 + 20
 
474
                        for i := 0; i < b.N; i++ {
 
475
                                for j := 0; j <= max; j++ {
 
476
                                        binary(tab, uint16(j))
 
477
                                }
 
478
                        }
 
479
                }
 
480
                bmlinear := testing.Benchmark(blinear)
 
481
                bmbinary := testing.Benchmark(bbinary)
 
482
                fmt.Printf("n=%d: linear=%d binary=%d\n", n, bmlinear.NsPerOp(), bmbinary.NsPerOp())
 
483
                return bmlinear.NsPerOp()*100 > bmbinary.NsPerOp()*110
 
484
        })
 
485
        fmt.Printf("calibration: linear cutoff = %d\n", n)
 
486
}
 
487
 
 
488
func fakeTable(n int) []Range16 {
 
489
        var r16 []Range16
 
490
        for i := 0; i < n; i++ {
 
491
                r16 = append(r16, Range16{uint16(i*5 + 10), uint16(i*5 + 12), 1})
 
492
        }
 
493
        return r16
 
494
}
 
495
 
 
496
func linear(ranges []Range16, r uint16) bool {
 
497
        for i := range ranges {
 
498
                range_ := &ranges[i]
 
499
                if r < range_.Lo {
 
500
                        return false
 
501
                }
 
502
                if r <= range_.Hi {
 
503
                        return (r-range_.Lo)%range_.Stride == 0
 
504
                }
 
505
        }
 
506
        return false
 
507
}
 
508
 
 
509
func binary(ranges []Range16, r uint16) bool {
 
510
        // binary search over ranges
 
511
        lo := 0
 
512
        hi := len(ranges)
 
513
        for lo < hi {
 
514
                m := lo + (hi-lo)/2
 
515
                range_ := &ranges[m]
 
516
                if range_.Lo <= r && r <= range_.Hi {
 
517
                        return (r-range_.Lo)%range_.Stride == 0
 
518
                }
 
519
                if r < range_.Lo {
 
520
                        hi = m
 
521
                } else {
 
522
                        lo = m + 1
 
523
                }
 
524
        }
 
525
        return false
 
526
}
 
527
 
 
528
func TestLatinOffset(t *testing.T) {
 
529
        var maps = []map[string]*RangeTable{
 
530
                Categories,
 
531
                FoldCategory,
 
532
                FoldScript,
 
533
                Properties,
 
534
                Scripts,
 
535
        }
 
536
        for _, m := range maps {
 
537
                for name, tab := range m {
 
538
                        i := 0
 
539
                        for i < len(tab.R16) && tab.R16[i].Hi <= MaxLatin1 {
 
540
                                i++
 
541
                        }
 
542
                        if tab.LatinOffset != i {
 
543
                                t.Errorf("%s: LatinOffset=%d, want %d", name, tab.LatinOffset, i)
 
544
                        }
 
545
                }
 
546
        }
 
547
}