- Zero Initialization
- Generic Data Structures
- Specialized Generic Data Structures
- Implementation Hiding
- Type Composition
This chapter is from the book
This chapter is from the book
This chapter is from the book
Specialized Generic Data Structures
33 func (s*stack) Push(vinterface{}) {
34 // Special case for integers
35 val := reflect.ValueOf(v)
36 if (val.Kind() == reflect.Int) {
37 i := val.Int()
38 if (s.isInteger) {
39 top := s.top.(*integerStackEntry)
40 if top.value == i {
41 top.count++
42 return
43 }
44 }
45 var e integerStackEntry
46 e.value = i
47 e.next = s.top
48 s.top = &e
49 s.isInteger = true;
50 } else {
51 var e genericStackEntry
52 e.value = v
53 e.next = s.top
54 s.top = &e
55 s.isInteger = false;
56 }
57 }
From: specializedStack.go
Suppose you wanted to use the stack from the last section in a push-down automaton. You’d probably be mainly pushing and popping integers, and often pushing the same integer several times in a row. There’s a large potential for optimization: you can have a specialized version of the stack entry that stores an integer and a count. If you push the same integer twice, then you just increment the count, saving the overhead of an allocation.
The example at the start of this section shows an expanded Push() method that does this. This now uses two types, one for the generic case and one for the integer case.
5 type stackEntry interface {
6 pop() (interface{}, stackEntry)
7 }
8 type genericStackEntry struct {
9 next stackEntry
10 value interface{}
11 }
12 func (g genericStackEntry) pop() (interface{},
stackEntry) {
13 return g.value, g.next
14 }
15 type integerStackEntry struct {
16 value int64
17 count int
18 next stackEntry
19 }
20 func (i*integerStackEntry) pop() (interface{},
stackEntry) {
21 if (i.count > 0) {
22 i.count--
23 return i.value, i
24 }
25 return i.value, i.next
26 }
From: specializedStack.go
When you push an integer, it uses the reflect packageto determine the type, and checks whether the last value to be pushed was an integer. In this case, it just increments the count. We’ll look in more detail at how to use the reflect package to identify the type of a value in Chapter 15, Interacting with the Go Runtime.
This example splits the specialized work up a bit between the generic data structure and the specialized components. You might want to modify it to add a tryPush() method to the stackEntry interface, which would try to add the value without adding a new stack entry. If this failed, then you could allocate a new entry of the same type.
This pattern shows one of the big advantages of the loose coupling that Go provides. The interface to the stack that uses a combination of genericStackEntry and integerStackEntry structures for its elements is completely compatible with the one from the last section, but is now more efficient for storing large sequences of identical integer values. The details of the two concrete structures implementing stack entries are completely hidden.
You can use this same approach to implement generic collections and then specialize them for your data. Complex collections in languages like Go typically incorporate this kind of self-optimizing behavior.
This is a fairly simple example and the saving in this case is not particularly worthwhile. This pattern is very useful in more complex data structures. For example, the underlying implementation of the map types uses a similar technique, generating a hash value based on the underlying type. You might want to do something similar, providing a built-in hash for basic types, using a zero hash by default, or using the Hash() method if one exists.