All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
ntesukiTable.cc
Go to the documentation of this file.
1 /* ntesukiTable.cc
2  */
10 #include "osl/record/csaRecord.h"
11 #ifdef NDEBUG
13 #endif
14 #include <iostream>
15 #include <queue>
16 #include <set>
17 
19 largeGCCount = 0;
20 
22 Table(unsigned int c,
23  unsigned int g,
24  bool v)
25  : ntesuki_hash_map(c), capacity(c), default_gc_size(g),
26  verbose(v), no_gc(false), gc_request(false),
27  numEntry(0), numCacheHit(0), gcCount(0)
28 {
29 }
30 
33 {
34 }
35 
38 allocate(const HashKey& key,
39  const PieceStand& white_stand,
40  signed short distance)
41 {
42  int full = 0;
43  reallocate:
44  if (numEntry < capacity || no_gc)
45  {
46  if (numEntry >= capacity) gc_request = true;
47  NtesukiRecord::RecordList *record_list =
48  &(ntesuki_hash_map::operator[](key.getSignatureKey()));
49  for (NtesukiRecord::RecordList::iterator p = record_list->begin();
50  p != record_list->end(); ++p)
51  {
52  if (p->key.getPieceStand() == key.getPieceStand())
53  {
54  ++numCacheHit;
55  return &(*p);
56  }
57  }
58 
59  ++numEntry;
60  const NtesukiRecord r(distance, key, white_stand, record_list);
61  record_list->push_front(r);
62  NtesukiRecord *result = &(record_list->front());
63  return result;
64  }
65 
66  NtesukiRecord *result = find(key);
67  if (result == 0 && full++ == 0 && capacity)
68  {
69  if (default_gc_size > 0)
70  {
71  collectGarbage(default_gc_size);
72  goto reallocate;
73  }
74  }
75  return result;
76 }
77 
79 {
81  const osl::ntesuki::NtesukiRecord *rhs)
82  {
83  return lhs->getChildCount() < rhs->getChildCount();
84  }
85 };
86 
88 {
89  /* Prints each node.
90  * Leaf nodes are not printed.
91  */
94  std::vector<osl::ntesuki::NtesukiRecord*> records;
95  std::set<HashKey> read_keys;
96  int depth, pass_count, pass_depth;
97 
101  : state(s), table(t),
102  depth(-1), pass_count(0)
103  {
104  }
105 
107  {
108  read_keys.insert(r->key);
109  records.push_back(r);
110  ++depth;
111  }
112  void exit()
113  {
114  read_keys.erase(records.back()->key);
115  records.pop_back();
116  if (pass_depth) pass_count--;
117  --depth;
118  }
121  {
122  if (move.isPass())
123  {
124  if (pass_count) return false;
125  pass_count++;
126  pass_depth = depth;
127  }
128 
129  if (read_keys.find(child->key) != read_keys.end())
130  {
131  return false;
132  }
133 
134  int i = 0;
135  for (; i <= depth; i++) std::cerr << "*";
136  std::cerr << record::csa::show(move.getMove());
137  for (; i <= 11; i++) std::cerr << " ";
138 
139  if (child->isVisited()) std::cerr << "(*)";
140  if (depth > 8)
141  {
142  std::cerr << "\t" << child->getChildCount() << "\t"
143  << child->getValue<BLACK>(0) << " \t"
144  << child->getValue<BLACK>(1) << " |\n";
145  return false;
146  }
147  else
148  {
149  std::cerr << "\t" << child->getChildCount() << "\t"
150  << child->getValue<BLACK>(0) << " \t"
151  << child->getValue<BLACK>(1) << "\n";
152  }
153  return true;
154  }
155 
157  {
158  }
159 
161  const osl::ntesuki::NtesukiMove& rhs)
162  {
163  osl::ntesuki::NtesukiRecord *record = records.back();
164  ntesuki_assert(record);
165  NtesukiRecord *lchild = table.find(record->key.newHashWithMove(lhs.getMove()));
166  if (!lchild) return false;
167  NtesukiRecord *rchild = table.find(record->key.newHashWithMove(rhs.getMove()));
168  if (!rchild) return true;
169 
170  if (lchild->isVisited()) return true;
171  if (rchild->isVisited()) return false;
172  return lchild->getChildCount() > rchild->getChildCount();
173  }
174  struct Compare
175  {
177  const osl::ntesuki::NtesukiMove& rhs)
178  {
179  return lhs.getMove() < rhs.getMove();
180  }
181  };
182 };
183 
185 {
186  /* Prints each node.
187  * Leaf nodes are printed as well.
188  */
189 
192  std::vector<osl::ntesuki::NtesukiRecord*> records;
193  std::set<HashKey> read_keys;
194  int depth, pass_count, pass_depth, depth_visited;
195 
199  : state(s), table(t),
200  depth(-1), pass_count(0), pass_depth(0), depth_visited(0)
201  {
202  }
203 
205  {
206  if (r->isVisited()) ++depth_visited;
207  read_keys.insert(r->key);
208  records.push_back(r);
209  ++depth;
210  }
211  void exit()
212  {
213  read_keys.erase(records.back()->key);
214  records.pop_back();
215  if (pass_depth) pass_count--;
216  --depth;
217  }
220  {
221  if (move.isPass())
222  {
223  if (pass_count) return false;
224  pass_count++;
225  pass_depth = depth;
226  }
227 
228  bool result = true;
229 
230  if (depth < depth_visited)
231  {
232  return false;
233  }
234 
235  int i = 0;
236  for (; i <= depth; i++) std::cerr << "*";
237  for (; i <= 10; i++) std::cerr << " ";
238  std::cerr << record::csa::show(move.getMove());
239  if (child->isVisited()) std::cerr << "(*)";
240  if (read_keys.find(child->key) != read_keys.end())
241  {
242  std::cerr << "loop";
243  result = false;
244  }
245 
246  std::cerr << "\t" << child->getChildCount() << "\t"
247  << child->getValue<osl::BLACK>(0) << "\t"
248  << child->getValue<osl::BLACK>(1) << "\n";
249 
250  return result;
251  }
252 
254  {
255  if (depth < depth_visited)
256  {
257  return;
258  }
259  int i = 0;
260  for (; i <= depth; i++) std::cerr << "*";
261  for (; i <= 10; i++) std::cerr << " ";
262  std::cerr << record::csa::show(move.getMove())
263  << "|\t"
264  << move.h_a_proof << "/" << move.h_a_disproof << "\t"
265  << move.h_d_proof << "/" << move.h_d_disproof
266  << "\n";
267  }
268 
270  const osl::ntesuki::NtesukiMove& rhs)
271  {
272  osl::ntesuki::NtesukiRecord *record = records.back();
273  ntesuki_assert(record);
274  NtesukiRecord *lchild = table.find(record->key.newHashWithMove(lhs.getMove()));
275  if (!lchild) return false;
276  NtesukiRecord *rchild = table.find(record->key.newHashWithMove(rhs.getMove()));
277  if (!rchild) return true;
278 
279  if (lchild->isVisited()) return true;
280  if (rchild->isVisited()) return false;
281  return lchild->getChildCount() > rchild->getChildCount();
282  }
283 
284  struct Compare
285  {
287  const osl::ntesuki::NtesukiMove& rhs)
288  {
289  return lhs.getMove() < rhs.getMove();
290  }
291  };
292 };
293 
294 struct
296 {
299  std::set<HashKey> reachable_keys;
300  int depth;
301 
305  : state(s), table(t)
306  {
307  }
308 
310  {
311  typedef std::vector<HashKey> keys_t;
312  keys_t garbage_list;
313  for (osl::ntesuki::NtesukiTable::Table::iterator it = table.begin();
314  it != table.end(); ++it)
315  {
316  for (NtesukiRecord::RecordList::iterator p = it->second.begin();
317  p != it->second.end(); ++p)
318  {
319  NtesukiRecord *record = &(*p);
320  if (reachable_keys.find(record->key) == reachable_keys.end())
321  {
322  garbage_list.push_back(record->key);
323  }
324  else
325  {
326  reachable_keys.erase(record->key);
327  }
328  }
329  }
330  for (keys_t::iterator it = garbage_list.begin();
331  it != garbage_list.end(); ++it)
332  {
333  table.erase(*it);
334  }
335  }
337  {
338  reachable_keys.insert(r->key);
339  }
340  void exit()
341  {
342  }
343 
346  {
347  return reachable_keys.find(child->key) == reachable_keys.end();
348  }
349 
351  {
352  }
353 
354  struct Compare
355  {
357  const osl::ntesuki::NtesukiMove& rhs)
358  {
359  return lhs.getMove() < rhs.getMove();
360  }
361  };
362 };
363 
364 void
366 collectGarbage(unsigned int gc_size)
367 {
368  if (gc_size == 0)
369  {
370  throw TableFull();
371  }
372  if (largeGCCount >= 0 &&
373  gcCount >= static_cast<unsigned int>(largeGCCount))
374  {
375  if (verbose)
376  {
377  std::cerr << "\ntoo many GCs, failing\n\n";
378  //forEachRecordFromRoot<RecordPrinter>();//DEBUG
379  }
380  throw TableFull();
381  }
382  ++gcCount;
383 #if 0
384  const unsigned int garbage_size = numEntry - gc_size;
385  if (verbose)
386  {
387  std::cerr << "GC: ";
388  for (int i = 0; i < 2; i++)
389  {
390  std::cerr << root->getValue<BLACK>(i) << "\t"
391  << root->getValue<WHITE>(i) << "\t";
392  }
393  std::cerr << " " << numEntry << " -> ";
394  }
395 
396  std::priority_queue<NtesukiRecord *,
397  std::vector<NtesukiRecord *>,
398  CompareChildSize> garbage_list;
399 
400  for (iterator it = begin(); it != end(); ++it)
401  {
402  for (NtesukiRecord::RecordList::iterator p = it->second.begin();
403  p != it->second.end(); ++p)
404  {
405  NtesukiRecord *record = &(*p);
406  if (record->isVisited()
407  //|| record->isFinal()
408  )
409  {
410  record->addChildCount(garbage_size);
411  continue;
412  }
413 
414  garbage_list.push(record);
415  if (garbage_list.size() > garbage_size)
416  {
417  garbage_list.pop();
418  }
419  }
420  }
421 
422  std::cerr << "\n*before GC\n";//DEBUG
423  //forEachRecordFromRoot<RecordPrinter>();//DEBUG
424  forEachRecordFromRoot<RecordPrinter2>();//DEBUG
425 
426  while (!garbage_list.empty())
427  {
428  NtesukiRecord *garbage = garbage_list.top();
429  erase(garbage->key);
430  garbage_list.pop();
431  }
432 
433  if (verbose)
434  {
435  std::cerr << numEntry << "\n";
436  }
437  std::cerr << "*after GC\n";//DEBUG
438  forEachRecordFromRoot<RecordPrinter2>();//DEBUG
439  //forEachRecordFromRoot<RecordPrinter>();//DEBUG
440  //throw TableFull();//DEBUG
441 #else
442  if (verbose)
443  {
444  std::cerr << "GC: ";
445  for (int i = 0; i < 2; i++)
446  {
447  std::cerr << root->getValue<BLACK>(i) << "\t"
448  << root->getValue<WHITE>(i) << "\t";
449  }
450  std::cerr << "\n";
451  }
452  //std::cerr << "\n*before GC\n";//DEBUG
453  //forEachRecordFromRoot<RecordPrinter>();//DEBUG
454  //forEachRecordFromRoot<RecordPrinter2>();//DEBUG
455 
456  unsigned int orig_size = numEntry;
457  unsigned int small_subtree_size = 1,
458  garbage_size = 0;
459  while (numEntry > gc_size)
460  {
461  for (iterator list_it = begin();
462  list_it != end(); ++list_it)
463  {
464  /* テーブルに登録された record の list について,
465  * リストの各要素の subtree のサイズを見て,必要なら collect する.
466  * ここでの list は所謂 same board list.
467  */
468 
469  /* 対象とする record が削除された場合には,その record への iterator は無効になるので,
470  * 先頭から調べ直す.
471  */
472  retry_collect_list:
473  for (NtesukiRecord::RecordList::iterator r = list_it->second.begin();
474  r != list_it->second.end(); ++r)
475  {
476  NtesukiRecord *record = &(*r);
477 
478  if (record->isVisited())
479  {
480  continue;
481  }
482  if (record->getChildCount() < small_subtree_size
483  && record->rev_refcount == 0)
484  {
485  ++garbage_size;
486  --numEntry;
487  for (NtesukiRecord::RecordPList::const_iterator pit = record->parents.begin();
488  pit != record->parents.end(); ++pit)
489  {
490  (*pit)->rev_refcount--;
491  }
492  list_it->second.erase(r); /* この時点で r は無効 */
493  goto retry_collect_list;
494  }
495  }
496  }
497 #ifdef MARK_AND_SWEEP_AFTER_SMALLTREEGC
498  unsigned int before_mark_and_sweep = numEntry;
499  forEachRecordFromRoot<MarkAndSweep>();
500  garbage_size += before_mark_and_sweep - numEntry;
501 #endif
502  //std::cerr << small_subtree_size << "\t" << garbage_size << "\t" << numEntry << "\n";//DEBUG
503  small_subtree_size += 4;
504  }
505  small_subtree_size -= 4;
506 
507  for (iterator it = begin(); it != end(); ++it)
508  {
509  for (NtesukiRecord::RecordList::iterator p = it->second.begin();
510  p != it->second.end(); ++p)
511  {
512  NtesukiRecord *record = &(*p);
513  if (record->isVisited())
514  {
515  record->addChildCount(garbage_size);
516  }
517  }
518  }
519 
520  if (verbose)
521  {
522  std::cerr << numEntry << "\tcollected up to " << small_subtree_size << "\n";
523  std::cerr << " " << orig_size << " -> " << numEntry << "\n";
524  }
525  //std::cerr << "*after GC\n";//DEBUG
526  //forEachRecordFromRoot<RecordPrinter2>();//DEBUG
527  //forEachRecordFromRoot<RecordPrinter>();//DEBUG
528  //if (largeGCCount >= 0 && gc_count >= largeGCCount) throw TableFull();//DEBUG
529  //throw TableFull();//DEBUG
530 #endif
531 }
532 
535 find(const HashKey& key)
536 {
537  ntesuki_hash_map::iterator hit =
538  ntesuki_hash_map::find(key.getSignatureKey());
539  if (hit == ntesuki_hash_map::end())
540  {
541  return 0;
542  }
543  for (NtesukiRecord::RecordList::iterator p = hit->second.begin();
544  p != hit->second.end(); ++p)
545  {
546  if (p->key.getPieceStand() == key.getPieceStand())
547  {
548  ++numCacheHit;
549  return &(*p);
550  }
551  }
552  return 0;
553 }
554 
555 void
557 erase(const HashKey key)
558 {
559  ntesuki_hash_map::iterator hit =
560  ntesuki_hash_map::find(key.getSignatureKey());
561  if (hit == ntesuki_hash_map::end())
562  {
563  return;
564  }
565  for (NtesukiRecord::RecordList::iterator p = hit->second.begin();
566  p != hit->second.end(); ++p)
567  {
568  if (p->key.getPieceStand() == key.getPieceStand())
569  {
570  hit->second.erase(p);
571  --numEntry;
572  return;
573  }
574  }
575 }
576 
578 NtesukiTable(unsigned int capacity,
579  unsigned int gc_size,
580  bool verbose)
581  : table(new Table(capacity, gc_size, verbose)),
582  verbose(verbose),
583  depths(200,0)
584  {}
585 
588 {
589  //forEachRecordFromRoot<RecordPrinter>();//DEBUG
590 
591  if (verbose)
592  {
593  std::cerr << "~NtesukiTable size " << size()
594  << ", cache hit " << table->numCacheHit
595  << ", table full " << table->gcCount << "\n";
596 
597  ntesuki_hash_map::const_iterator hit = this->begin();
598  while (hit != this->end())
599  {
600  const NtesukiRecord::RecordList& record_list = hit->second;
601  for (NtesukiRecord::RecordList::const_iterator p = record_list.begin();
602  p != record_list.end(); ++p)
603  {
604  const NtesukiRecord& r = *p;
605  const unsigned short d = r.distance;
606  if (d >= 200)
607  {
608  std::cerr << d << r << "\n";
609  }
610  depths[d]++;
611  }
612  hit++;
613  }
614 
615  for (int depth = 0; depth < 200; depth++)
616  {
617  if (depths[depth] != 0)
618  {
619  std::cerr << "depth: " << depth << " " << depths[depth] << "\n";
620  }
621  }
622  }
623 }
624 
626 isVerbose() const
627 {
628  return verbose;
629 }
630 /* ------------------------------------------------------------------------- */
631 // ;;; Local Variables:
632 // ;;; mode:c++
633 // ;;; c-basic-offset:2
634 // ;;; End: