Home > Articles > Programming

  • Print
  • + Share This
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.

  • + Share This
  • 🔖 Save To Your Account