Rietveld Code Review Tool
Help | Bug tracker | Discussion group | Source code | Sign in
(2830)

Delta Between Two Patch Sets: src/pkg/compress/bzip2/move_to_front.go

Issue 131840043: code review 131840043: bzip2: improve performance (Closed)
Left Patch Set: Created 9 years, 7 months ago
Right Patch Set: diff -r 3cf190969915d6d531acd0795eb81974aaa64d19 https://go.googlecode.com/hg/ Created 9 years, 7 months ago
Left:
Right:
Use n/p to move between diff chunks; N/P to move between comments. Please Sign in to add in-line comments.
Jump to:
Right: Side by side diff | Download
« no previous file with change/comment | « src/pkg/compress/bzip2/bzip2_test.go ('k') | no next file » | no next file with change/comment »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
LEFTRIGHT
(no file at all)
1 // Copyright 2011 The Go Authors. All rights reserved. 1 // Copyright 2011 The Go Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style 2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file. 3 // license that can be found in the LICENSE file.
4 4
5 package bzip2 5 package bzip2
6 6
7 // moveToFrontDecoder implements a move-to-front list. Such a list is an 7 // moveToFrontDecoder implements a move-to-front list. Such a list is an
8 // efficient way to transform a string with repeating elements into one with 8 // efficient way to transform a string with repeating elements into one with
9 // many small valued numbers, which is suitable for entropy encoding. It works 9 // many small valued numbers, which is suitable for entropy encoding. It works
10 // by starting with an initial list of symbols and references symbols by their 10 // by starting with an initial list of symbols and references symbols by their
11 // index into that list. When a symbol is referenced, it's moved to the front 11 // index into that list. When a symbol is referenced, it's moved to the front
12 // of the list. Thus, a repeated symbol ends up being encoded with many zeros, 12 // of the list. Thus, a repeated symbol ends up being encoded with many zeros,
13 // as the symbol will be at the front of the list after the first access. 13 // as the symbol will be at the front of the list after the first access.
14 type moveToFrontDecoder struct { 14 type moveToFrontDecoder []byte
15 » // Rather than actually keep the list in memory, the symbols are stored
16 » // as a circular, double linked list with the symbol indexed by head
17 » // at the front of the list.
18 » symbols [256]byte
19 » next [256]uint8
20 » prev [256]uint8
21 » head uint8
22 » len int
23 }
24 15
25 // newMTFDecoder creates a move-to-front decoder with an explicit initial list 16 // newMTFDecoder creates a move-to-front decoder with an explicit initial list
26 // of symbols. 17 // of symbols.
27 func newMTFDecoder(symbols []byte) *moveToFrontDecoder { 18 func newMTFDecoder(symbols []byte) moveToFrontDecoder {
28 if len(symbols) > 256 { 19 if len(symbols) > 256 {
29 panic("too many symbols") 20 panic("too many symbols")
30 } 21 }
31 22 » return moveToFrontDecoder(symbols)
32 » m := new(moveToFrontDecoder)
33 » copy(m.symbols[:], symbols)
34 » m.len = len(symbols)
35 » m.threadLinkedList()
36 » return m
37 } 23 }
38 24
39 // newMTFDecoderWithRange creates a move-to-front decoder with an initial 25 // newMTFDecoderWithRange creates a move-to-front decoder with an initial
40 // symbol list of 0...n-1. 26 // symbol list of 0...n-1.
41 func newMTFDecoderWithRange(n int) *moveToFrontDecoder { 27 func newMTFDecoderWithRange(n int) moveToFrontDecoder {
42 if n > 256 { 28 if n > 256 {
43 panic("newMTFDecoderWithRange: cannot have > 256 symbols") 29 panic("newMTFDecoderWithRange: cannot have > 256 symbols")
44 } 30 }
45 31
46 » m := new(moveToFrontDecoder) 32 » m := make([]byte, n)
47 for i := 0; i < n; i++ { 33 for i := 0; i < n; i++ {
48 » » m.symbols[byte(i)] = byte(i) 34 » » m[i] = byte(i)
49 } 35 }
50 » m.len = n 36 » return moveToFrontDecoder(m)
51 » m.threadLinkedList()
52 » return m
53 } 37 }
54 38
55 // threadLinkedList creates the initial linked-list pointers. 39 func (m moveToFrontDecoder) Decode(n int) (b byte) {
56 func (m *moveToFrontDecoder) threadLinkedList() { 40 » // Implement move-to-front with a simple copy. This approach
57 » if m.len == 0 { 41 » // beats more sophisticated approaches in benchmarking, probably
58 » » return 42 » // because it has high locality of reference inside of a
59 » } 43 » // single cache line (most move-to-front operations have n < 64).
60 44 » b = m[n]
61 » m.prev[0] = uint8(m.len - 1) 45 » copy(m[1:], m[:n])
62 46 » m[0] = b
63 » for i := byte(0); int(i) < m.len-1; i++ {
64 » » m.next[i] = uint8(i + 1)
65 » » m.prev[i+1] = uint8(i)
66 » }
67
68 » m.next[m.len-1] = 0
69 }
70
71 func (m *moveToFrontDecoder) Decode(n int) (b byte) {
72 » // Most of the time, n will be zero so it's worth dealing with this
73 » // simple case.
74 » if n == 0 {
75 » » return m.symbols[m.head]
76 » }
77
78 » i := m.head
79 » for j := 0; j < n; j++ {
80 » » i = m.next[i]
81 » }
82 » b = m.symbols[i]
83
84 » m.next[m.prev[i]] = m.next[i]
85 » m.prev[m.next[i]] = m.prev[i]
86 » m.next[i] = m.head
87 » m.prev[i] = m.prev[m.head]
88 » m.next[m.prev[m.head]] = i
89 » m.prev[m.head] = i
90 » m.head = i
91
92 return 47 return
93 } 48 }
94 49
95 // First returns the symbol at the front of the list. 50 // First returns the symbol at the front of the list.
96 func (m *moveToFrontDecoder) First() byte { 51 func (m moveToFrontDecoder) First() byte {
97 » return m.symbols[m.head] 52 » return m[0]
98 } 53 }
LEFTRIGHT

Powered by Google App Engine
RSS Feeds Recent Issues | This issue
This is Rietveld f62528b