Database And Brain

Segmentation Fault In Recurisve Structure With Smart Pointer

MD — Sat, 10 Jul 2010 04:47:50 +0000

A singly linked list implemented with smart pointer, which has a reference to next, can easily cause Stack Overflow at its destruction because the destructor of the next, and the next, and the next, are called recursively.

Here's the code.

Code:

#include <boost/shared_ptr.hpp>
#include <iostream>
 
#define RECURSIVE
 
class IntSLLNode {
 
private:
  int index;
  boost::shared_ptr<IntSLLNode> next;
 
  IntSLLNode(int ix){
    index = ix;
  }
 
public:
  int hasNext(){return next != 0;}
  boost::shared_ptr<IntSLLNode>& moveNext(){return next;}
  int getIndex(){return index;}
  friend class IntSLList;
};
 
class IntSLList {
private:
  boost::shared_ptr<IntSLLNode> head, tail;
public:  
  ~IntSLList(){
#ifndef RECURSIVE
    while(head != tail){
      // replace
      head = head->next;
    }
#endif
  }
 
  void addNode(int index){
 
    boost::shared_ptr<IntSLLNode> n(new IntSLLNode(index));
    if(head == 0){
      head = tail =n;
    }
    else
    {
      tail->next = n;
      tail = n;
    }
 
  }
 
  boost::shared_ptr<IntSLLNode>& getHeadNode(){return head;}
};
 
int main(){
  IntSLList list;
  // the number to reproduce crush may vary, but seems to be stable
  // On my Core2Duo box, it is around 65000
  // Here I dare to use a value large enough
  for(int i=0; i<1000000; i++){
    list.addNode(i);
  }
  // crush at destruction
  std::cout << "CRUSH?" << std::endl; 
}

This works by commenting out the line 4.

For your own smart pointer, the point is line 7 in the following code.

Code:

SmartPointer& operator=(const SmartPointer& src){
    if(this != &src){
      if(counter->decrement() == 0){
        delete counter;
        //src.pointee_ = 0; // NOT DESTRUCTIVE
        counter = src.counter;
        counter->increment(); // increment before deleting pointee_, which might have a reference to src. This results in a temporal no referencer, and triggers recursive destruction
        if(pointee_) delete pointee_;
        pointee_ = src.pointee_;
      }else{
        pointee_ = src.pointee_;
        //src.pointee_ = 0; // NOT DESTRUCTIVE
        counter = src.counter;
        counter->increment();
      }
    }
    return *this;
  }

If you call delete pointee_ before incrementing the counter of src, it triggers recursive destruction in the above case.

For a large graph cached in memory, it's good to have some kind of protection or grouping methods.

Original post blogged on b2evolution.

So far, so bad.

MD — Fri, 09 Jul 2010 06:31:12 +0000

I found a couple of things. A couple of bad things.

~~1. shared_ptr is not thread safe~~ * it was stack overflow by recursive destruction

Here's the code to reproduce. The reason follows.

SPIntSLList.h

Code:

#ifndef INT_SINGLY_LINKEDLIST
#define INT_SINGLY_LINKEDLIST
 
#include <boost/shared_ptr.hpp>
 
class SPIntSLLNode {
 
private:
  int index;
  long int payload[4];
  boost::shared_ptr<SPIntSLLNode> next;
 
  SPIntSLLNode(int ix){
    index = ix;
  }
 
public:
  int hasNext(){return next != 0;}
  boost::shared_ptr<SPIntSLLNode>& moveNext(){return next;}
  int getIndex(){return index;}
  friend class SPIntSLList;
};
 
class SPIntSLList {
private:
  boost::shared_ptr<SPIntSLLNode> head, tail;
public:  
  ~SPIntSLList();
 
  void addNode(int index);
  boost::shared_ptr<SPIntSLLNode>& getHeadNode(){return head;}
};
 
#endif

SPIntSLList.cpp

Code:

#include <iostream>
#include <time.h>
#include "SPIntSLList.h"
 
SPIntSLList::~SPIntSLList(){
  // no need iterative deletion
}
 
void SPIntSLList::addNode(int index){
  boost::shared_ptr<SPIntSLLNode> n(new SPIntSLLNode(index));
  if(head == 0){
    head = n;
    tail = n;
  }
  else
  {
    tail->next = n;
    tail = n;
  }
}
 
int main(){
 
  std::cout << "sizeof(SPIntSLLNode) = " << sizeof(SPIntSLLNode) << std::endl;
 
  clock_t start, end;
 
  std::cout << "creating huge large SPIntSLList" << std::endl;
  start = clock();
  SPIntSLList huge;
  std::cout << "creating huge SPIntSLListNode" << std::endl;
  // 157160: segmetation fault boarder when load was evaluated
  for(int i=0; i<1000000; i++){
    huge.addNode(i);
    // n, temporal PSP is destructed here
  }
  end = clock();
  std::cout << "creation time: " << (end-start) << " clocks(" << (double) (end-start)/CLOCKS_PER_SEC << " sec)" << std::endl; 
 
  std::cout << "iterating over huge SPIntSLListNode" << std::endl;
  start = clock();
  // the following code calls copy constructor instead of assignment operator
  boost::shared_ptr<SPIntSLLNode> current = huge.getHeadNode();
  while(current->hasNext()){
    if(current->getIndex() % 10000 == 0)
      std::cout << "index:" << current->getIndex() << std::endl;
    current = current->moveNext();
  }
  end = clock();
  std::cout << "iteration time: " << (end-start) << " clocks(" << (double) (end-start)/CLOCKS_PER_SEC << " sec)" << std::endl; 
  std::cout << "completed huge SPIntSLList" << std::endl;
}

Then, a wonderful gift.

Segmentation fault (core dumped)

And here's the stack trace.

Code:

Program terminated with signal 11, Segmentation fault.
#0  0x0000000000401227 in boost::detail::atomic_exchange_and_add (pw=Cannot access memory at address 0x7fff2ee2dff8
)
    at /home/takenori/workspace_native/Boost/boost/smart_ptr/detail/sp_counted_base_gcc_x86.hpp:36
36      {
(gdb) bt
#0  0x0000000000401227 in boost::detail::atomic_exchange_and_add (pw=Cannot access memory at address 0x7fff2ee2dff8
)
    at /home/takenori/workspace_native/Boost/boost/smart_ptr/detail/sp_counted_base_gcc_x86.hpp:36
#1  0x000000000040137b in boost::detail::sp_counted_base::release (
    this=0xd921130)
    at /home/takenori/workspace_native/Boost/boost/smart_ptr/detail/sp_counted_base_gcc_x86.hpp:143
#2  0x000000000040142b in boost::detail::shared_count::~shared_count (
    this=0xd9210c0, __in_chrg=<value optimized out>)
    at /home/takenori/workspace_native/Boost/boost/smart_ptr/detail/shared_count.hpp:217
#3  0x00000000004014be in boost::shared_ptr<SPIntSLLNode>::~shared_ptr (
    this=0xd9210b8, __in_chrg=<value optimized out>)
    at /home/takenori/workspace_native/Boost/boost/smart_ptr/shared_ptr.hpp:163

They have the same mistake as mine.

Code:

~shared_count() // nothrow
    {
       if( pi_ != 0 ) pi_->release();
#if defined(BOOST_SP_ENABLE_DEBUG_HOOKS)
        id_ = 0;
#endif
    }

After "pi_ != 0", pi is not guarranteed to stay valid. It is possible to delete after its evaluation.

The last two referencing threads can enter release().

Code:

void release() // nothrow
    {
        if( atomic_exchange_and_add( &use_count_, -1 ) == 1 )
        {
            dispose();
            weak_release();
        }
    }

Then, one comes late experiences Segmentation Fault on $use_count_.

2. Atomic types and operations are not as fast as RCU(read copy update)

I expected this(from the presentation by liburcu).

But the performance of lock-free reference counting smart pointer is as slow as mutex, on my dual core linux box.

The difference might be less significant because it's only dual core on 1 CPU. But I doubt it.

The test was like this.

Code:

#include "TsPersistentSmartPointer.h"
#include <iostream>
#include <time.h>
 
#define MAX_THREADS  100
#define ITERATION  1000
 
class Foo{
public:
  Foo(int id) : id_(id){std::cout << id_ << ":constructer called" << std::endl;}
  ~Foo(){std::cout << id_ << ":destructer called" << std::endl;}
 
  void SayHello(){
    std::cout << "Hello, this is " << id_ << std::endl;
  }
private:
  int id_;
};
 
void *copy(void *arg){
  // 1. copy, adding a reference
  TsPersistentSmartPointer<Foo> psp = *((TsPersistentSmartPointer<Foo>*) arg);
  TsPersistentSmartPointer<Foo> pspCopied = psp;
 
  // 2. removing a reference when exiting
}
 
int main(){
  
  TsPersistentSmartPointer<Foo> psp(new Foo(3));
  pthread_t threads[MAX_THREADS];
  int rt;
 
  clock_t start, end;
  std::cout << "Executing..." << std::endl;
  start = clock();
  for(int i=0; i<ITERATION; i++)
  {
    for(int t=0; t<MAX_THREADS; t++){
      rt = pthread_create(&threads[t], NULL, copy, (void*) &psp);
      if(rt != 0){
        std::cout << "Failed to create thread " << t << std::endl;
      }
    }
 
    for(int t=0; t<MAX_THREADS; t++){
      rt = pthread_join(threads[t], NULL);
      if(rt != 0){
        std::cout << "Failed to join thread " << t << std::endl;
      }
    }
  }
 
  end = clock();
  std::cout << "execution time: " << (end-start) << " clocks(" << (double) (end-start)/CLOCKS_PER_SEC << " sec)" << std::endl; 
}

This is heavily read intensive test. But each read on reference counting SmartPointer requires incrementing the counter, and decrementing when exiting. So it is deadly heavy write intensive test. It would run as low as Mutex in the figure above.

liburcu is implemented with architecture specific assembly code. But what's the difference? That's what I ought to find...

Original post blogged on b2evolution.

Lock-free reference counting smart pointer

MD — Thu, 08 Jul 2010 05:05:33 +0000

With GCC 4.4, I tested how atomic types and operations of c++0x work by implementing lock-free reference counting smart pointer.

TsPersistentSmartPointer.h

Code:

#ifndef PERSISTENT_SMART_POINTER
#define PERSISTENT_SMART_POINTER
 
#include <cstdatomic>
 
class Counter {
public:
  Counter():i(1){}
  ~Counter(){}
 
  void increment(){
    i.fetch_add( 1, std::memory_order_relaxed );
  }
  int decrement(){
    return i.fetch_sub( 1, std::memory_order_relaxed );
  }
  void reset(){
    i.store(0, std::memory_order_relaxed);
  }
private:
  std::atomic_uint i;
};
 
template <class T>
class TsPersistentSmartPointer {
public:
  explicit TsPersistentSmartPointer(T* pointee) : pointee_(pointee), counter(new Counter()){
  }
  TsPersistentSmartPointer() : pointee_(0), counter(new Counter()){
  }; // for null construction, has to be copied from somewhere else
  ~TsPersistentSmartPointer(){
    if(counter->decrement() == 0){
      delete counter;
      delete pointee_;
    }
  }
 
  T& operator*() const{
    return *pointee_; 
  }
 
  T* operator->() const{
    return pointee_; 
  }
 
  // assignment
  TsPersistentSmartPointer(const TsPersistentSmartPointer& src){
      pointee_ = src.pointee_;
      counter = src.counter;
      counter->increment();
      //src.pointee_ = 0; // NOT DESTRUCTIVE
  }
  TsPersistentSmartPointer& operator=(const TsPersistentSmartPointer& src){
    if(this != &src){
      if(counter->decrement() == 0){
        delete counter;
        if(pointee_) delete pointee_;
      }
      pointee_ = src.pointee_;
      //src.pointee_ = 0; // NOT DESTRUCTIVE
      counter = src.counter;
      counter->increment();
    }
    return *this;
  }
  TsPersistentSmartPointer& operator=(T* pointee){
    if(pointee_ != pointee){
      if(pointee_)
        delete pointee_;
      pointee_ = pointee;
      counter->reset();
    }
    return *this;
  }
 
  // equality
  inline friend bool operator==(const TsPersistentSmartPointer& psp, const T* pointee){
    return psp.pointee_ == pointee;
  }
  inline friend bool operator==(const T* pointee, const TsPersistentSmartPointer& psp){
    return pointee == psp.pointee_;
  }
  // inequality
  inline friend bool operator!=(const TsPersistentSmartPointer& psp, const T* pointee){
    return psp.pointee_ != pointee;
  }
  inline friend bool operator!=(const T* pointee, const TsPersistentSmartPointer& psp){
    return pointee != psp.pointee_;
  }
 
private:
  T* pointee_;
  Counter* counter;
};
 
#endif

Atomic operations are implemented inside Counter class. The point is the following part, the destructor of TsPersistentSmartPointer:

Code:

if(counter->decrement() == 0){
      delete counter;
      delete pointee_;
    }

At first, I did the following, which resulted in Segmentation Fault under a million of concurrent destructions.

Code:

counter->decrement();
    if(counter->get() == 0){
      delete counter;
      delete pointee_;
    }

The problem could happen when the last two enters concurrently.

Thread1: counter->decrement(); // i = 1
Thread2: counter->decrement(); // i = 0
Thread2: counter->get() == 0 // TRUE
Thread1: counter->get() == 0 // TRUE!
Thread1: delete counter;
Thread2: delete counter; // OUCH!

Here're some more code for testing.

TsPersistentSmartPointer.cpp

Code:

#include "TsPersistentSmartPointer.h"
#include <iostream>
 
class Foo{
public:
  Foo(int id) : id_(id){std::cout << id_ << ":constructer called" << std::endl;}
  ~Foo(){std::cout << id_ << ":destructer called" << std::endl;}
 
  void SayHello(){
    std::cout << "Hello, this is " << id_ << std::endl;
  }
private:
  int id_;
};
 
int main(){
 
  Foo f0(0);
  Foo *f1 = new Foo(1);
  Foo *f2 = new Foo(2); // memory leak
  Foo *f3 = new Foo(3);
  TsPersistentSmartPointer<Foo> psp(0);
 
  // copy
  psp = f3;
 
  // dereference and indirection
  psp->SayHello();
  (*psp).SayHello();
 
  // equality
  std::cout << "equality works? :" << ((psp == f3) & (f3 == psp)) << std::endl;
 
  // copy constructor
  TsPersistentSmartPointer<Foo> pspCopied(psp);
  // dereference and indirection
  pspCopied->SayHello();
  (*pspCopied).SayHello();
 
  // see how destructors are called
  delete f1;
 
  return 0;
}

TsPSPIntSLList.h

Code:

#ifndef INT_SINGLY_LINKEDLIST
#define INT_SINGLY_LINKEDLIST
 
#include "TsPersistentSmartPointer.h"
 
class TsPSPIntSLLNode {
 
private:
  int index;
  long int payload[4];
  TsPersistentSmartPointer<TsPSPIntSLLNode> next;
 
  TsPSPIntSLLNode(int ix){
    index = ix;
  }
 
public:
  int hasNext(){return next != 0;}
  TsPersistentSmartPointer<TsPSPIntSLLNode>& moveNext(){return next;}
  int getIndex(){return index;}
  friend class TsPSPIntSLList;
};
 
class TsPSPIntSLList {
private:
  TsPersistentSmartPointer<TsPSPIntSLLNode> head, tail;
public:  
  ~TsPSPIntSLList();
 
  void addNode(int index);
  TsPersistentSmartPointer<TsPSPIntSLLNode>& getHeadNode(){return head;}
};
 
#endif

TsPSPIntSLList.cpp

Code:

#include <iostream>
#include <time.h>
#include "TsPSPIntSLList.h"
 
TsPSPIntSLList::~TsPSPIntSLList(){
  // no need iterative deletion
}
 
void TsPSPIntSLList::addNode(int index){
  TsPersistentSmartPointer<TsPSPIntSLLNode> n(new TsPSPIntSLLNode(index));
  if(head == 0){
    head = n;
    tail = n;
  }
  else
  {
    tail->next = n;
    tail = n;
  }
}
 
int main(){
 
  std::cout << "sizeof(TsPSPIntSLLNode) = " << sizeof(TsPSPIntSLLNode) << std::endl;
 
  clock_t start, end;
 
  std::cout << "creating huge large TsPSPIntSLList" << std::endl;
  start = clock();
  TsPSPIntSLList huge;
  std::cout << "creating huge TsPSPIntSLListNode" << std::endl;
  // 157160: segmetation fault boarder when load was evaluated
  for(int i=0; i<1000000; i++){
    huge.addNode(i);
    // n, temporal PSP is destructed here
  }
  end = clock();
  std::cout << "creation time: " << (end-start) << " clocks(" << (double) (end-start)/CLOCKS_PER_SEC << " sec)" << std::endl; 
 
  std::cout << "iterating over huge TsPSPIntSLListNode" << std::endl;
  start = clock();
  // the following code calls copy constructor instead of assignment operator
  TsPersistentSmartPointer<TsPSPIntSLLNode> current = huge.getHeadNode();
  while(current->hasNext()){
    if(current->getIndex() % 10000 == 0)
      std::cout << "index:" << current->getIndex() << std::endl;
    current = current->moveNext();
  }
  end = clock();
  std::cout << "iteration time: " << (end-start) << " clocks(" << (double) (end-start)/CLOCKS_PER_SEC << " sec)" << std::endl; 
  std::cout << "completed huge TsPSPIntSLList" << std::endl;
 
  // followings are called automatically, but here explicitely for measurement
  //current.~TsPersistentSmartPointer();
  //huge.~TsPSPIntSLList();
 
}

Please note no code is required for the destructor of TsPersistentSmartPointer.

So what about reference linking?

No. It can't be lock free if with doubly linked list. Two links to prev and next have to be updated at the same time, otherwise one could see inconsistent stete.

Performance?

I have measured performance with clock() function defined in "time.h" as in TsPSPIntSLList.cpp.

Raw Pointer for single thread
Creation: 0.01 sec
Iteration: 0.02 sec

SmartPointer for single thread
Creation: 0.27 sec
Iteration: 0.05 sec

Lock-free SmartPointer
Creation: 0.45 sec
Iteration: 0.12 sec

In time, there's a significant overhead over plain raw pointer implementation.

Also, a couple of CPU cache statistics collected by vaigrind.

Raw Pointer for single thread
Instruction Read: 409,523,865
Data Read: 115,388,899
L1 Data Read Miss: 2,013,421
L2 Data Read Miss: 2,005,354
Data Write: 69,133,007
L1 Data Write Miss: 1,002,531
L2 Data Write Miss: 1,001,018

Smart Pointer for single thread
Instruction Read: 960,359,665
Data Read: 284,618,659
L1 Data Read Miss: 2,049,844
L2 Data Read Miss: 2,041,472
Data Write: 172,410,809
L1 Data Write Miss: 1,916,330
L2 Data Write Miss: 1,914,709

Lock-free Smart Pointer
Instruction Read: 1,161,535,161
Data Read: 317,391,770
L1 Data Read Miss: 2,013,687
L2 Data Read Miss: 2,005,198
Data Write: 235,134,100
L1 Data Write Miss: 2,002,377
L2 Data Write Miss: 2,001,012

(pthread Mutex SmartPointer)
Creation: 0.51 sec
Iteration: 0.14 sec
Instruction Read: 1,149,615,787
Data Read: 311,412,927
L1 Data Read Miss: 3,014,567
L2 Data Read Miss: 3,005,312
Data Write: 237,144,326
L1 Data Write Miss: 3,002,797
L2 Data Write Miss: 3,001,194

Please note L1 and L2 cache read miss stays around as total number increases.
(except mutex: mutex calls another million of malloc)

It is not free lunch. But for read intensive applications, how attractive it is!

Original post blogged on b2evolution.

A Solution To Von Neumann bottleneck

MD — Sun, 23 May 2010 08:27:39 +0000

Here's a question.

Do you have a problem about memory performance that might have been observed as CPU or I/O bottleneck before?

In other words,

Where's your interests about performance bottleneck today? Memory?

Even like this:

Do you use any Virtualization technology?

If yes, you are likely suffering from Von Neumann bottleneck, which is described as follows in Wikipedia:

The separation between the CPU and memory leads to the von Neumann bottleneck, the limited throughput (data transfer rate) between the CPU and memory compared to the amount of memory.

This is not something new, but is considered having been accelerated by increasing number of CPU cores and size of RAM, while having almost the same amount of cache and the same bus size between memory and CPU.

Intel released Xeon 7500 series(e.g. X7560) recently. It has NUMA architecture, which has respective dedicated memory bank and bus to each CPU. OS kernels have improved memory management system like SLAB to achieve better cache hit rate from CPU point's of view.

But, inherently, memory allocation is a responsibility of a programmer. A compiler can optimize instructions, but not data manipulated. Today's CPU can predict repeated pattern, but which is extremely simple like a jump.

So, I could say, the third factor, that has accelerated the bottleneck, is a programmer.

Object Database is a technology developed long time ago. And its benefit has been considered development efficiency through maximum utilization of Object Oriented Programming Language.

Recently, I found one possible huge benefit of Object Database that has not been addressed before.

ODBMS returns objects that are directly referenced by a user against a query. While returned values are copied to user objects with RDBMS. In this sense, ODBMS provides memory management system. While it is up to a programmer with RDBMS.

So, here's the potential that ODBMS can be a solution to Von Neumann bottleneck.

From CPU's point of view, cache is nothing but bringing data up to L1 by the time CPU process it.

L1 <- L2
(L2 <- L3)
L2 <- RAM
(TLB lookup)
(physical address <- virtual address)
(RAM <- I/O: disk or network)

So, I could say, ODBMS is a cache system.

This can explain up to 100x times faster performance on complex data structure like Graph.

Such a redefinition might unveil the true power of ODBMS.

Original post blogged on b2evolution.

Object Database As Memory Management System

MD — Fri, 16 Apr 2010 06:02:46 +0000

Object Database has survived for no particular reason. There's an obvious case that Object Database overwhelms other database systems both in performance and productivity.

It is where non-predeterministic query is issued, often in an algorithm.

For example, any algorithms on a Graph are good examples. Suppose you have a practical, optimized shortest path search algorithm. Which verteces you need to retrieve?

Unknown.

Until its previous vertex is evaluated.

So, in this case, it takes too long if it gets done straightforward. With RDBMS, you need to issue a query for every single vertex. That involves heavy tasks like disk and network access. While Object Database can prefetch/cluster them according to their relations. That will save those two heavy tasks down to 1/(prefetch_size * cache_hit_rate). Of course it gets worse if cache_hit_rate is too low, though.

The benefit is significant. In some particular cases. That's why 10 out of 10 US telecom uses Versant.

So, now I am wondering if we can extend the benefit.

Last year, in game industry, there was a trend called Data Oriented Design.

The Latency Elephant.

Until recently, we didn't doubt the best strategy was to bring data onto memory. It is almost the fastest. But it is not true anymore.

It looks like the same thing as described above between client and server happens between memory and CPU. When you zoom in by 1000x(compared to client/server), you'll see there's a long way.

The solution is obvious. To put related objects together on a single page so that cache miss won't happen. The result is shown in the same way, 1/(prefetch_size * cache_hit_rate), compared to the worst scenario(every object is on a different page from each other).

It is obvious, but not easy. OS hids physical representation and only present logical representation both in file and memory allocation. So, you have to roll the abstraction carpet, and go down.

But what about sending Object Database down there, and let it manage. It must be effective not only for existing users, but also for Memory Management System in general.

Original post blogged on b2evolution.

What character do you think of about "A.I."?

MD — Thu, 25 Mar 2010 02:34:40 +0000

Obviously, it is monotonous. One, single profile. Like "Star Wars Episode II". Those clones.

Also, often questioned if it has a mind or not. In Japan, there're many that have minds to help people against evils.

Oops, is it a robot? Robot isn't it "A.I."?

Definition.

"the study and design of intelligent agents," where an intelligent agent is a system that perceives its environment and takes actions that maximize its chances of success.

Okay, so "A.I." has a goal by definition, lives to achieve a goal. This sounds, nothing to do with "intelligence". Or, "intelligence" is an ability to achieve a goal!?

Again, the definition.

Intelligence is an umbrella term describing a property of the mind comprehending related abilities, such as the capacities for abstract thought, reasoning, planning, problem solving, speech, and learning.

A property of the mind. But it should not be of oneself, but of others. It is "others" that think someone as "INTELLIGENT".

So, it doesn't matter if it has mind or is clever and perfect.

Is it safe to redefine "INTELLIGENT" as "RELIABLE"? You can count on it. Then, it is "INTELLIGENT". Like us for human, it is not entirely, but on a specific field/situation. "RELIABLE" needs a small print.

No, but are we "RELIABLE"? No. I could label us "NOT RELIABLE".

Yet, we can accept it. Then, we can get along with.

We expect something perfect. But nothing. Plus and Minus. Up and Down. I guess, it's easier to get along with such a "NOT RELIABLE". Someone perfect must be empty or too disciplined.

So, I guess we have an ability to recognize a certain character. It is a key. Then, we can get along with. A "character". It seems to be the realistic and helpful direction of "A.I.".

Original post blogged on b2evolution.

Infinite loop on a finite state machine

MD — Wed, 24 Mar 2010 03:43:09 +0000

Finite State Machine and Behavior Tree are often used in game AI. In game, designer asks expected actions to give users expected experience. So, generic offerings like machine learning is somewhat useless because it lacks control.

But there IS a difficulty in decision making. What action to take at when? There're many possibilities.

State --> Action --> Path Finding, Movement, etc. A1 A2 A3 A4 PC S1 S2 S3 S4 S5 S6 S7 S8 a1 a2 a3 a4 NPC s1 s2 s3 s4 s5 s6 s7 s8 Action: A, a State: S, s * current in bold Actions may be ordered by behavior trees. States may be directed. In FSM, there's only one state at a time, and is designed as directed graph.

So, in this case,
Decision Making is done as "Pick up an action or a chain of actions based on current states". And what leads to better decision making?

In FSM, for example in FPS, state is simple. In combat or not. Whenever NPC become aware of PC, it gets in combat mode to kill you. But the action could be complicated. Which path to get closer? With obstacles to hide? Can work as a team? Evaluation function? More variables gets you less control. If NPC is damn zombie, sending more zombies with damn pathfinder makes sense. But if it is not, it seems another layer of state machine is required. And, that would require another, and another, and another...

It may not help, but think about ourselves. We, human, does this in three stages.

-Define Goal
Often, defining goal is not easy. It is not plain, but hierarchical. In team, we share it.
-Observe
Collect information to describe the current situation towards the goal.
-Analyse
Analyse collected information, and list possible actions.

Wrong analysis on less information or wrong information likely leads to failure.

This happens also in game. Information given is limited both in its amount and its realtime ness due to system resource. Even if information is enough, the situation may not be obvious.

But a game is basically zero-sum game. I mean, there is an opponent. So if you know what the opponent does, you can choose a winning option. But if the opponent knows it, it can choose a counter solution. And if, and if, and if...

Now it seems we are in an infinite loop on a finite state machine. This may represent a common argue, "WE NEED MORE PROCESSING POWER". Seriously?

A sniper will put most of its efforts on collecting information. A soldier on actions to give more damages. If there is a diversity in NPC abilities, which fates its character, their fights to take their advantages to achieve their goals become a game. Doesn't it become an expectation of what your team mates do? Like, one tend to stay back and cover, another to go first and lead. That kind of character makes game play a lot easier to work with and more fun to fight against NPCs.

A character, an expectation, to count on others, simplifies decision making. PC reveals its character, too, through actions made in the past, which makes team play easier, and prevent bad users from the community to keep game experience.

Original post blogged on b2evolution.

NPC Training College

MD — Fri, 19 Mar 2010 02:50:37 +0000

NPC stands for Non Player Character, which moves autonomously. Here's the definition in WIkipedia.

What's for? To have NPC experienced. Then apply the experience to another.
What's needed? Reusability.
What's possible in the future? NPC will forcast, recognize differences from the actual happenings, then concentrait on the current situation(increase sensitibity rather than forcast) to achieve the goal. And it becomes an experience.

NPC:
has a goal.
can recognize the situation.
then make an action.

NPC will:
forcast.
recognize the differences from events actually happened.
concentrait to sense the situation to deal with unknown situation.

Underlying Theorem: Bayes' Theorem
1. Improve prior probability(by expert, by machine learning)
2. Collect posterior to have it experienced
Situation is modeled as Bayesian network. Then, makes an action.

The problem: Reusability
Raw sense information is too concrete to be reused.

Solution: Multiple sense layers(Hierarchical Baysian network )
According to "On INTELLIGENCE, Jeff Hawkins", human neo cortex is layered. HIgher a layer is, more abstracted information is. So sensing happens bottom-up, while forcast happens up-down.

Mmmm, this contains lots of tasks unresolved. I need to focus. But, this is an interesting project to have AI experienced by open, community based efforts.

Original post blogged on b2evolution.

	`#include <boost/shared_ptr.hpp>`
	`#include <iostream>`

	`#define RECURSIVE`

	`class IntSLLNode {`

	`private:`
	`int index;`
	`boost::shared_ptr<IntSLLNode> next;`

	`IntSLLNode(int ix){`
	`index = ix;`
	`}`

	`public:`
	`int hasNext(){return next != 0;}`
	`boost::shared_ptr<IntSLLNode>& moveNext(){return next;}`
	`int getIndex(){return index;}`
	`friend class IntSLList;`
	`};`

	`class IntSLList {`
	`private:`
	`boost::shared_ptr<IntSLLNode> head, tail;`
	`public:`
	`~IntSLList(){`
	`#ifndef RECURSIVE`
	`while(head != tail){`
	`// replace`
	`head = head->next;`
	`}`
	`#endif`
	`}`

	`void addNode(int index){`

	`boost::shared_ptr<IntSLLNode> n(new IntSLLNode(index));`
	`if(head == 0){`
	`head = tail =n;`
	`}`
	`else`
	`{`
	`tail->next = n;`
	`tail = n;`
	`}`

	`}`

	`boost::shared_ptr<IntSLLNode>& getHeadNode(){return head;}`
	`};`

	`int main(){`
	`IntSLList list;`
	`// the number to reproduce crush may vary, but seems to be stable`
	`// On my Core2Duo box, it is around 65000`
	`// Here I dare to use a value large enough`
	`for(int i=0; i<1000000; i++){`
	`list.addNode(i);`
	`}`
	`// crush at destruction`
	`std::cout << "CRUSH?" << std::endl;`
	`}`

	`SmartPointer& operator=(const SmartPointer& src){`
	`if(this != &src){`
	`if(counter->decrement() == 0){`
	`delete counter;`
	`//src.pointee_ = 0; // NOT DESTRUCTIVE`
	`counter = src.counter;`
	`counter->increment(); // increment before deleting pointee_, which might have a reference to src. This results in a temporal no referencer, and triggers recursive destruction`
	`if(pointee_) delete pointee_;`
	`pointee_ = src.pointee_;`
	`}else{`
	`pointee_ = src.pointee_;`
	`//src.pointee_ = 0; // NOT DESTRUCTIVE`
	`counter = src.counter;`
	`counter->increment();`
	`}`
	`}`
	`return *this;`
	`}`

	`#ifndef INT_SINGLY_LINKEDLIST`
	`#define INT_SINGLY_LINKEDLIST`

	`#include <boost/shared_ptr.hpp>`

	`class SPIntSLLNode {`

	`private:`
	`int index;`
	`long int payload[4];`
	`boost::shared_ptr<SPIntSLLNode> next;`

	`SPIntSLLNode(int ix){`
	`index = ix;`
	`}`

	`public:`
	`int hasNext(){return next != 0;}`
	`boost::shared_ptr<SPIntSLLNode>& moveNext(){return next;}`
	`int getIndex(){return index;}`
	`friend class SPIntSLList;`
	`};`

	`class SPIntSLList {`
	`private:`
	`boost::shared_ptr<SPIntSLLNode> head, tail;`
	`public:`
	`~SPIntSLList();`

	`void addNode(int index);`
	`boost::shared_ptr<SPIntSLLNode>& getHeadNode(){return head;}`
	`};`

	`#endif`

	`#include <iostream>`
	`#include <time.h>`
	`#include "SPIntSLList.h"`

	`SPIntSLList::~SPIntSLList(){`
	`// no need iterative deletion`
	`}`

	`void SPIntSLList::addNode(int index){`
	`boost::shared_ptr<SPIntSLLNode> n(new SPIntSLLNode(index));`
	`if(head == 0){`
	`head = n;`
	`tail = n;`
	`}`
	`else`
	`{`
	`tail->next = n;`
	`tail = n;`
	`}`
	`}`

	`int main(){`

	`std::cout << "sizeof(SPIntSLLNode) = " << sizeof(SPIntSLLNode) << std::endl;`

	`clock_t start, end;`

	`std::cout << "creating huge large SPIntSLList" << std::endl;`
	`start = clock();`
	`SPIntSLList huge;`
	`std::cout << "creating huge SPIntSLListNode" << std::endl;`
	`// 157160: segmetation fault boarder when load was evaluated`
	`for(int i=0; i<1000000; i++){`
	`huge.addNode(i);`
	`// n, temporal PSP is destructed here`
	`}`
	`end = clock();`
	`std::cout << "creation time: " << (end-start) << " clocks(" << (double) (end-start)/CLOCKS_PER_SEC << " sec)" << std::endl;`

	`std::cout << "iterating over huge SPIntSLListNode" << std::endl;`
	`start = clock();`
	`// the following code calls copy constructor instead of assignment operator`
	`boost::shared_ptr<SPIntSLLNode> current = huge.getHeadNode();`
	`while(current->hasNext()){`
	`if(current->getIndex() % 10000 == 0)`
	`std::cout << "index:" << current->getIndex() << std::endl;`
	`current = current->moveNext();`
	`}`
	`end = clock();`
	`std::cout << "iteration time: " << (end-start) << " clocks(" << (double) (end-start)/CLOCKS_PER_SEC << " sec)" << std::endl;`
	`std::cout << "completed huge SPIntSLList" << std::endl;`
	`}`

	`Program terminated with signal 11, Segmentation fault.`
	`#0 0x0000000000401227 in boost::detail::atomic_exchange_and_add (pw=Cannot access memory at address 0x7fff2ee2dff8`
	`)`
	`at /home/takenori/workspace_native/Boost/boost/smart_ptr/detail/sp_counted_base_gcc_x86.hpp:36`
	`36 {`
	`(gdb) bt`
	`#0 0x0000000000401227 in boost::detail::atomic_exchange_and_add (pw=Cannot access memory at address 0x7fff2ee2dff8`
	`)`
	`at /home/takenori/workspace_native/Boost/boost/smart_ptr/detail/sp_counted_base_gcc_x86.hpp:36`
	`#1 0x000000000040137b in boost::detail::sp_counted_base::release (`
	`this=0xd921130)`
	`at /home/takenori/workspace_native/Boost/boost/smart_ptr/detail/sp_counted_base_gcc_x86.hpp:143`
	`#2 0x000000000040142b in boost::detail::shared_count::~shared_count (`
	`this=0xd9210c0, __in_chrg=<value optimized out>)`
	`at /home/takenori/workspace_native/Boost/boost/smart_ptr/detail/shared_count.hpp:217`
	`#3 0x00000000004014be in boost::shared_ptr<SPIntSLLNode>::~shared_ptr (`
	`this=0xd9210b8, __in_chrg=<value optimized out>)`
	`at /home/takenori/workspace_native/Boost/boost/smart_ptr/shared_ptr.hpp:163`

	`~shared_count() // nothrow`
	`{`
	`if( pi_ != 0 ) pi_->release();`
	`#if defined(BOOST_SP_ENABLE_DEBUG_HOOKS)`
	`id_ = 0;`
	`#endif`
	`}`

	`void release() // nothrow`
	`{`
	`if( atomic_exchange_and_add( &use_count_, -1 ) == 1 )`
	`{`
	`dispose();`
	`weak_release();`
	`}`
	`}`

	`#include "TsPersistentSmartPointer.h"`
	`#include <iostream>`
	`#include <time.h>`

	`#define MAX_THREADS 100`
	`#define ITERATION 1000`

	`class Foo{`
	`public:`
	`Foo(int id) : id_(id){std::cout << id_ << ":constructer called" << std::endl;}`
	`~Foo(){std::cout << id_ << ":destructer called" << std::endl;}`

	`void SayHello(){`
	`std::cout << "Hello, this is " << id_ << std::endl;`
	`}`
	`private:`
	`int id_;`
	`};`

	`void copy(void arg){`
	`// 1. copy, adding a reference`
	`TsPersistentSmartPointer<Foo> psp = ((TsPersistentSmartPointer<Foo>) arg);`
	`TsPersistentSmartPointer<Foo> pspCopied = psp;`

	`// 2. removing a reference when exiting`
	`}`

	`int main(){`

	`TsPersistentSmartPointer<Foo> psp(new Foo(3));`
	`pthread_t threads[MAX_THREADS];`
	`int rt;`

	`clock_t start, end;`
	`std::cout << "Executing..." << std::endl;`
	`start = clock();`
	`for(int i=0; i<ITERATION; i++)`
	`{`
	`for(int t=0; t<MAX_THREADS; t++){`
	`rt = pthread_create(&threads[t], NULL, copy, (void*) &psp);`
	`if(rt != 0){`
	`std::cout << "Failed to create thread " << t << std::endl;`
	`}`
	`}`

	`for(int t=0; t<MAX_THREADS; t++){`
	`rt = pthread_join(threads[t], NULL);`
	`if(rt != 0){`
	`std::cout << "Failed to join thread " << t << std::endl;`
	`}`
	`}`
	`}`

	`end = clock();`
	`std::cout << "execution time: " << (end-start) << " clocks(" << (double) (end-start)/CLOCKS_PER_SEC << " sec)" << std::endl;`
	`}`

	`#ifndef PERSISTENT_SMART_POINTER`
	`#define PERSISTENT_SMART_POINTER`

	`#include <cstdatomic>`

	`class Counter {`
	`public:`
	`Counter():i(1){}`
	`~Counter(){}`

	`void increment(){`
	`i.fetch_add( 1, std::memory_order_relaxed );`
	`}`
	`int decrement(){`
	`return i.fetch_sub( 1, std::memory_order_relaxed );`
	`}`
	`void reset(){`
	`i.store(0, std::memory_order_relaxed);`
	`}`
	`private:`
	`std::atomic_uint i;`
	`};`

	`template <class T>`
	`class TsPersistentSmartPointer {`
	`public:`
	`explicit TsPersistentSmartPointer(T* pointee) : pointee_(pointee), counter(new Counter()){`
	`}`
	`TsPersistentSmartPointer() : pointee_(0), counter(new Counter()){`
	`}; // for null construction, has to be copied from somewhere else`
	`~TsPersistentSmartPointer(){`
	`if(counter->decrement() == 0){`
	`delete counter;`
	`delete pointee_;`
	`}`
	`}`

	`T& operator*() const{`
	`return *pointee_;`
	`}`

	`T* operator->() const{`
	`return pointee_;`
	`}`

	`// assignment`
	`TsPersistentSmartPointer(const TsPersistentSmartPointer& src){`
	`pointee_ = src.pointee_;`
	`counter = src.counter;`
	`counter->increment();`
	`//src.pointee_ = 0; // NOT DESTRUCTIVE`
	`}`
	`TsPersistentSmartPointer& operator=(const TsPersistentSmartPointer& src){`
	`if(this != &src){`
	`if(counter->decrement() == 0){`
	`delete counter;`
	`if(pointee_) delete pointee_;`
	`}`
	`pointee_ = src.pointee_;`
	`//src.pointee_ = 0; // NOT DESTRUCTIVE`
	`counter = src.counter;`
	`counter->increment();`
	`}`
	`return *this;`
	`}`
	`TsPersistentSmartPointer& operator=(T* pointee){`
	`if(pointee_ != pointee){`
	`if(pointee_)`
	`delete pointee_;`
	`pointee_ = pointee;`
	`counter->reset();`
	`}`
	`return *this;`
	`}`

	`// equality`
	`inline friend bool operator==(const TsPersistentSmartPointer& psp, const T* pointee){`
	`return psp.pointee_ == pointee;`
	`}`
	`inline friend bool operator==(const T* pointee, const TsPersistentSmartPointer& psp){`
	`return pointee == psp.pointee_;`
	`}`
	`// inequality`
	`inline friend bool operator!=(const TsPersistentSmartPointer& psp, const T* pointee){`
	`return psp.pointee_ != pointee;`
	`}`
	`inline friend bool operator!=(const T* pointee, const TsPersistentSmartPointer& psp){`
	`return pointee != psp.pointee_;`
	`}`

	`private:`
	`T* pointee_;`
	`Counter* counter;`
	`};`

	`#endif`

	`counter->decrement();`
	`if(counter->get() == 0){`
	`delete counter;`
	`delete pointee_;`
	`}`

	`#include <iostream>`
	`#include <time.h>`
	`#include "TsPSPIntSLList.h"`

	`TsPSPIntSLList::~TsPSPIntSLList(){`
	`// no need iterative deletion`
	`}`

	`void TsPSPIntSLList::addNode(int index){`
	`TsPersistentSmartPointer<TsPSPIntSLLNode> n(new TsPSPIntSLLNode(index));`
	`if(head == 0){`
	`head = n;`
	`tail = n;`
	`}`
	`else`
	`{`
	`tail->next = n;`
	`tail = n;`
	`}`
	`}`

	`int main(){`

	`std::cout << "sizeof(TsPSPIntSLLNode) = " << sizeof(TsPSPIntSLLNode) << std::endl;`

	`clock_t start, end;`

	`std::cout << "creating huge large TsPSPIntSLList" << std::endl;`
	`start = clock();`
	`TsPSPIntSLList huge;`
	`std::cout << "creating huge TsPSPIntSLListNode" << std::endl;`
	`// 157160: segmetation fault boarder when load was evaluated`
	`for(int i=0; i<1000000; i++){`
	`huge.addNode(i);`
	`// n, temporal PSP is destructed here`
	`}`
	`end = clock();`
	`std::cout << "creation time: " << (end-start) << " clocks(" << (double) (end-start)/CLOCKS_PER_SEC << " sec)" << std::endl;`

	`std::cout << "iterating over huge TsPSPIntSLListNode" << std::endl;`
	`start = clock();`
	`// the following code calls copy constructor instead of assignment operator`
	`TsPersistentSmartPointer<TsPSPIntSLLNode> current = huge.getHeadNode();`
	`while(current->hasNext()){`
	`if(current->getIndex() % 10000 == 0)`
	`std::cout << "index:" << current->getIndex() << std::endl;`
	`current = current->moveNext();`
	`}`
	`end = clock();`
	`std::cout << "iteration time: " << (end-start) << " clocks(" << (double) (end-start)/CLOCKS_PER_SEC << " sec)" << std::endl;`
	`std::cout << "completed huge TsPSPIntSLList" << std::endl;`

	`// followings are called automatically, but here explicitely for measurement`
	`//current.~TsPersistentSmartPointer();`
	`//huge.~TsPSPIntSLList();`

	`}`