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