FST  openfst-1.7.1
OpenFst Library
arc-arena.h
Go to the documentation of this file.
1 #ifndef FST_ARC_ARENA_H_
2 #define FST_ARC_ARENA_H_
3 
4 #include <deque>
5 #include <memory>
6 #include <utility>
7 #include <fst/fst.h>
8 #include <fst/memory.h>
9 #include <unordered_map>
10 
11 namespace fst {
12 
13 // ArcArena is used for fast allocation of contiguous arrays of arcs.
14 //
15 // To create an arc array:
16 // for each state:
17 // for each arc:
18 // arena.PushArc();
19 // // Commits these arcs and returns pointer to them.
20 // Arc *arcs = arena.GetArcs();
21 //
22 // OR
23 //
24 // arena.DropArcs(); // Throws away current arcs, reuse the space.
25 //
26 // The arcs returned are guaranteed to be contiguous and the pointer returned
27 // will never be invalidated until the arena is cleared for reuse.
28 //
29 // The contents of the arena can be released with a call to arena.Clear() after
30 // which the arena will restart with an initial allocation capable of holding at
31 // least all of the arcs requested in the last usage before Clear() making
32 // subsequent uses of the Arena more efficient.
33 //
34 // The max_retained_size option can limit the amount of arc space requested on
35 // Clear() to avoid excess growth from intermittent high usage.
36 template <typename Arc>
37 class ArcArena {
38  public:
39  explicit ArcArena(size_t block_size = 256,
40  size_t max_retained_size = 1e6)
41  : block_size_(block_size),
42  max_retained_size_(max_retained_size) {
43  blocks_.emplace_back(MakeSharedBlock(block_size_));
44  first_block_size_ = block_size_;
45  total_size_ = block_size_;
46  arcs_ = blocks_.back().get();
47  end_ = arcs_ + block_size_;
48  next_ = arcs_;
49  }
50 
51  ArcArena(const ArcArena& copy)
52  : arcs_(copy.arcs_), next_(copy.next_), end_(copy.end_),
53  block_size_(copy.block_size_),
54  first_block_size_(copy.first_block_size_),
55  total_size_(copy.total_size_),
56  max_retained_size_(copy.max_retained_size_),
57  blocks_(copy.blocks_) {
58  NewBlock(block_size_);
59  }
60 
61  void ReserveArcs(size_t n) {
62  if (next_ + n < end_) return;
63  NewBlock(n);
64  }
65 
66  void PushArc(const Arc& arc) {
67  if (next_ == end_) {
68  size_t length = next_ - arcs_;
69  NewBlock(length * 2);
70  }
71  *next_ = arc;
72  ++next_;
73  }
74 
75  const Arc* GetArcs() {
76  const auto *arcs = arcs_;
77  arcs_ = next_;
78  return arcs;
79  }
80 
81  void DropArcs() { next_ = arcs_; }
82 
83  size_t Size() { return total_size_; }
84 
85  void Clear() {
86  blocks_.resize(1);
87  if (total_size_ > first_block_size_) {
88  first_block_size_ = std::min(max_retained_size_, total_size_);
89  blocks_.back() = MakeSharedBlock(first_block_size_);
90  }
91  total_size_ = first_block_size_;
92  arcs_ = blocks_.back().get();
93  end_ = arcs_ + first_block_size_;
94  next_ = arcs_;
95  }
96 
97  private:
98  // Allocates a new block with capacity of at least n or block_size,
99  // copying incomplete arc sequence from old block to new block.
100  void NewBlock(size_t n) {
101  const auto length = next_ - arcs_;
102  const auto new_block_size = std::max(n, block_size_);
103  total_size_ += new_block_size;
104  blocks_.emplace_back(MakeSharedBlock(new_block_size));
105  std::copy(arcs_, next_, blocks_.back().get());
106  arcs_ = blocks_.back().get();
107  next_ = arcs_ + length;
108  end_ = arcs_ + new_block_size;
109  }
110 
111  std::shared_ptr<Arc> MakeSharedBlock(size_t size) {
112  return std::shared_ptr<Arc>(new Arc[size], std::default_delete<Arc[]>());
113  }
114 
115  Arc *arcs_;
116  Arc *next_;
117  const Arc *end_;
118  size_t block_size_;
119  size_t first_block_size_;
120  size_t total_size_;
121  size_t max_retained_size_;
122  std::list<std::shared_ptr<Arc>> blocks_;
123 };
124 
125 // ArcArenaStateStore uses a resusable ArcArena to store arc arrays and does not
126 // require that the Expander call ReserveArcs first.
127 //
128 // TODO(tombagby): Make cache type configurable.
129 // TODO(tombagby): Provide ThreadLocal/Concurrent configuration.
130 template <class A>
132  public:
133  using Arc = A;
134  using Weight = typename Arc::Weight;
135  using StateId = typename Arc::StateId;
136 
137  ArcArenaStateStore() : arena_(64 * 1024) {
138  }
139 
140  class State {
141  public:
142  Weight Final() const { return final_; }
143 
144  size_t NumInputEpsilons() const { return niepsilons_; }
145 
146  size_t NumOutputEpsilons() const { return noepsilons_; }
147 
148  size_t NumArcs() const { return narcs_; }
149 
150  const Arc &GetArc(size_t n) const { return arcs_[n]; }
151 
152  const Arc *Arcs() const { return arcs_; }
153 
154  int* MutableRefCount() const { return nullptr; }
155 
156  private:
157  State(Weight weight, int32 niepsilons, int32 noepsilons, int32 narcs,
158  const Arc *arcs)
159  : final_(std::move(weight)),
160  niepsilons_(niepsilons),
161  noepsilons_(noepsilons),
162  narcs_(narcs),
163  arcs_(arcs) {}
164 
165  Weight final_;
166  size_t niepsilons_;
167  size_t noepsilons_;
168  size_t narcs_;
169  const Arc *arcs_;
170 
171  friend class ArcArenaStateStore<Arc>;
172  };
173 
174  template <class Expander>
175  State *FindOrExpand(Expander &expander, StateId state_id) { // NOLINT
176  auto it = cache_.insert(std::pair<StateId, State*>(state_id, nullptr));
177  if (!it.second) return it.first->second;
178  // Needs a new state.
179  StateBuilder builder(&arena_);
180  expander.Expand(state_id, &builder);
181  const auto arcs = arena_.GetArcs();
182  size_t narcs = builder.narcs_;
183  size_t niepsilons = 0;
184  size_t noepsilons = 0;
185  for (size_t i = 0; i < narcs; ++i) {
186  if (arcs[i].ilabel == 0) ++niepsilons;
187  if (arcs[i].olabel == 0) ++noepsilons;
188  }
189  states_.emplace_back(
190  State(builder.final_, niepsilons, noepsilons, narcs, arcs));
191  // Places it in the cache.
192  auto state = &states_.back();
193  it.first->second = state;
194  return state;
195  }
196 
197  State *Find(StateId state_id) const {
198  auto it = cache_.find(state_id);
199  return (it == cache_.end()) ? nullptr : it->second;
200  }
201 
202  private:
203  class StateBuilder {
204  public:
205  explicit StateBuilder(ArcArena<Arc>* arena)
206  : arena_(arena), final_(Weight::Zero()), narcs_(0) {}
207 
208  void SetFinal(Weight weight) { final_ = std::move(weight); }
209 
210  void ReserveArcs(size_t n) { arena_->ReserveArcs(n); }
211 
212  void AddArc(const Arc &arc) {
213  ++narcs_;
214  arena_->PushArc(arc);
215  }
216 
217  private:
218  friend class ArcArenaStateStore<Arc>;
219 
220  ArcArena<Arc> *arena_;
221  Weight final_;
222  size_t narcs_;
223  };
224 
225  std::unordered_map<StateId, State *> cache_;
226  std::deque<State> states_;
227  ArcArena<Arc> arena_;
228 };
229 
230 } // namespace fst
231 
232 #endif // FST_ARC_ARENA_H_
typename Arc::StateId StateId
Definition: arc-arena.h:135
void PushArc(const Arc &arc)
Definition: arc-arena.h:66
typename Arc::Weight Weight
Definition: arc-arena.h:134
void Clear()
Definition: arc-arena.h:85
const Arc * Arcs() const
Definition: arc-arena.h:152
size_t Size()
Definition: arc-arena.h:83
size_t NumOutputEpsilons() const
Definition: arc-arena.h:146
const Arc & GetArc(size_t n) const
Definition: arc-arena.h:150
void DropArcs()
Definition: arc-arena.h:81
int * MutableRefCount() const
Definition: arc-arena.h:154
State * Find(StateId state_id) const
Definition: arc-arena.h:197
int32_t int32
Definition: types.h:26
ArcArena(size_t block_size=256, size_t max_retained_size=1e6)
Definition: arc-arena.h:39
State * FindOrExpand(Expander &expander, StateId state_id)
Definition: arc-arena.h:175
void ReserveArcs(size_t n)
Definition: arc-arena.h:61
ArcArena(const ArcArena &copy)
Definition: arc-arena.h:51
const Arc * GetArcs()
Definition: arc-arena.h:75
size_t NumInputEpsilons() const
Definition: arc-arena.h:144