Monday, May 16, 2011 | By: Kunal Ekawde

vtable usage understanding

Assuming that virtual function concept is clear, I would like to jot down some understanding with respect to use of vtable in virtual function call.

Every class which has a virtual function or is derived from the class which has, has a vtable. Its created by the compiler. For information, you can see the vtable created for the class using the g++ option '-fdump-class-hierarchy'. In the new generated file *.class file, check the Vtable.

For example for following c++ program:
class Base
{
public:
Base(){cout<<"In Base Ctor"<<endl;}
virtual ~Base() {cout<<"In Base Dtor"<<endl;}
virtual void b1() {cout<<"Base b1"<<endl;}
virtual int b2() {cout<<"Base b2"<<endl;}
void b3(int x) {cout<<"Base b2"<<endl;}
};

class Derived
{
public:
Derived() {cout<<"In Drvd Ctor"<<endl;}
~Derived() {cout<<"In Drvd Dtor"<<endl;}
void b1() {cout<<"Drvd b1"<<endl;}
void b1(int x) {cout<<"Drvd b1 x"<<endl;}
//int b1() {} --> Compile Error
virtual void d1() {cout<<"Drvd d1"<<endl;}
};
The vtable for Base and Derived would be:
Vtable for Base
Base::_ZTV4Base: 6u entries
0 (int (*)(...))0
4 (int (*)(...))(& _ZTI4Base)
8 Base::~Base
12 Base::~Base
16 Base::b1
20 Base::b2

Vtable for Derived
Derived::_ZTV7Derived: 7u entries
0 (int (*)(...))0
4 (int (*)(...))(& _ZTI7Derived)
8 Derived::~Derived
12 Derived::~Derived
16 Derived::b1
20 Base::b2
24 Derived::d1

  • The First entry is the offset to top of the actual object being pointed to from the location of vptr of current used (L-Part) object. Its 0 for single inheritance. In multiple level inheritance e.g class Derived:public Base1,public Base2 and Base2* pb2 = new Derived(), when the this pointer is adjusted to Base2 part location in Derived object and during re-adjusting it back, it has to know to which object(size) it was adjusted, which can be known by RTTI information, which in-turn can be located after starting location of that object.
  • The Second entry points to typeinfo object used for RTTI.
  • Third and Fourth entries are for virtual destructor, the first one destructs object w/o calling delete(), while the second calls the delete() after destroying object.
  • Fifth entry is of virtual function b1(), which is override 'd by the Derived class, each vtable has its own separate address.
  • Sixth entry is of b2(), which is not defined in Derived, but inherited and hence both vtables have same address.
  • Seventh entry is present in Derived class as a new virtual function is defined.
Now, suppose we have the following:
I)
Base* bptr = new Derived();
bptr->b1();
To find which instance of b1() has to be called:
1. bptr points to Base part in Derived object.In case of single inheritance, its pointing to Derived.
2. The function b1() is called via bptr(w/o any casting) so vtable has to be consulted.
3. The compiler knows that for b1(), it has to access the fifth location and its vptr is pointing to the actual referenced object i.e Derived.
4. Hence, (16 Derived::b1) is called.

II)
Consider:
bptr->d1();
This would give compile error, as in bptr type(Base), the function d1() is not known. Even though bptr is pointing to Derived object and its vtable has d1(), the compiler restricts it to types in pointer type(Base) as bptr = new Base();bptr->d1() could also be possible then but its an incorrect call.

III)
Line 18 in the program would give compile error as with same function arguments we are trying to override the b1() function with different return type, while Line 17 is fine, as the function signature is different and hence Derived class is not overriding it.

IV)
Virtual destructor works in same fashion as virtual function, once Derived destructor is called, the base is also followed. Logic to call Base could be in destructor of Derived.

V)
Virtual functions should not be called in constructors and destructors. Mainly 2 things:
(a) When the base part of derived object is being created, the derived members are not initialized yet.
(b) When the base part of derived object is being created, the this pointer belongs to the current class i.e base, the virtual functions, RTTI belongs to current class.
During destruction, the derived is first destructed and then Base,(derived part no longer exist) therefore in base destructor, the virtual function points to that of base only.

VI)Incase we have a Base w/o any virtual function (with some data members --to make its offset different from Derived) and Derived has and we delete a base pointer pointer to Derived object, the program would dump core. --> This was quite an interesting point for me. I've discussed it here. Basically, free will try to put the entire Derived object in free list, thereby disturbing the admin block of next chunk of data, hence the core dump, instead if Base had virtual destructor, the this pointer is adjusted after destructor of Derived and it cleanly free's the Base and Derived part.
Tuesday, April 12, 2011 | By: Kunal Ekawde

Dynamic Programming Basics

This is very interesting programming / algorithm problem solving technique.
There is a lot of information on this from bing/google about theory and some examples.

What I would like to post is, working example code with some explanation.

Lets consider a simple problem:
Prob) Find the largest strictly increasing continuous sub-sequence from the given sequence.

e.g Seq: 4,5,1,6,3,6,7,9,2,4

Here as we see that increasing sub-sequences are:
1) 4,5
2) 1,6
3) 3,6,7,9
4) 2,4

Hence, the largest turns out to be 3)3,6,7,9
In brute-force / general logic, we would find a max length at each index.
e.g Start at 4, 4>5, max length at 4 is 1, proceed further, compare 4 with 1, 4>1, so the max length remains same(1) else increment it.

Here is C code for same:

int IncSeq::getLargestSeq1(string &seq)
{
cout<< " Seq:"<<seq<<endl;
int maxLen = seq.length();
int i=0,j=0,cnt=0,s=0,max=0,len=0;
for (i=0; i<maxLen; i++)
{
cnt = 0;
s=i;
for (j=i+1; j <maxLen-1; j++)
{
if ( seq[j] > seq[s] )
{
len = ++cnt;
s++;
}
else
break;
}
if (len>max)
max = len;
}
return max;
}
The algorithm takes O(N2).
If we notice, the problem can be divided into sub-problems (on lines of dynamic programming) of find the increasing length from each of the index. At each index we compare the index element with next element and accordingly increment the number.
If we separate the inner loop as follows:

int IncSeq::increasingLenFromIndexM(int i, string &seq, int maxLen)
{
if (maxLen == 0)
return 0;

if ( seq[i+1] > seq[i] )
return 1+increasingLenFromIndexM(i+1, seq, maxLen);
else
return 0;
}

So we see here that if objective of seq[i+1]>seq[i] is satisfied, add to result the next sub-problems result. You can use it as:

int IncSeq::getLargestSeq1(string &seq)
{
cout<< " Seq:"<<seq<<endl;
int maxLen = seq.length();
int i=0,max=0,len=0;

for (i=0; i<maxLen; i++)
{
len = increasingLenFromIndexM(i, seq, maxLen);
if (len>max)
max = len;
}

return max;
}
Another property of dynamic programming is to memoise the answers to sub-problems so that we don't solve them again in recursion. The simplest is to save the answers in an array/table and check it at entry of every sub-problem as follows:

int IncSeq::increasingLenFromIndexM(int i,
string &seq, int maxLen)
{
int res =0;
if (maxLen == 0)
return 0;

if (ans[i]!=0)
return ans[i];

if ( seq[i+1] > seq[i] )
res = 1+increasingLenFromIndexM(i+1, seq, maxLen);
else
res = 0;

ans[i] = res;
return res;
}
Now if you see, it boils down to filling the table with answers of sub-problems.
What if start filling the table backward ? , then we can completely skip memoising the answers.

void IncSeq::dFillAnswers(vector<int>& A, int N)
{
ans[N]=0;

for (int i=N-2; i>=0; i-=1)
{
if ( A[i] < A[i+1] )
ans[i]=1+ans[i+1];
else
ans[i]=0;
}
}
and in function "increasingLenFromIndexM" just return the ans[index].
Thus we have solved the problem using dynamic programming
Friday, May 7, 2010 | By: Kunal Ekawde

Radix Patricia and Ternary datastructures

The efficiency of the process depends on the data structures and operations used in it. I had a chance to visit and implement Radix trie, Patricia trie and Ternary search trees.

Radix trie mostly associated with numeric data works on bit string representation of the key. Every node has a index set based on the difference of first bit encountered with previous key. Every next insert this bit position is checked for: if greater -> traverse right, else ->traverse left. Then set its bit position.

Patricia trie mostly associated with alphanumeric data works same as radix trie with one way branching removed(standard definition on internet). I shall post the implementation soon.

Ternary search tree also supports alpha numeric data set, with a each node having pointers to 3 nodes:right, left and equal. The full word comes under equal, if the character compared is greater, it becomes right node else left node. Although you may find insert and find operations, delete was not available on internet.

Here is the my current implementation and invitation to let me know bugs:
https://sourceforge.net/projects/ternarytree/files/

Thursday, May 6, 2010 | By: Kunal Ekawde

CPU analysis; sar system data and top data

On the current project i had a good opportunity for capacity testing of the product.
sar data was collected on each blade using cron, which is configurable using /etc/cron.d/sysstat.
sa1 would collect the OS statistics (counters) from different resources including /proc/stat etc. sa2 would decode the sar data collected (stored at /var/log/sa/) at a time specified in the above mentioned config file.
top data would be instant data collected, though one can run a moving average on top specifying the -n option. sar command can also be run at regular instants, but the values would be average over the delay the command is executed while the system wide would be moving average.
The sar data collected at instants can be compared to top data collected at instants and same with moving average.

Trip to coorg

It was our first anniversary and a trip away from Bangalore was already in my mind. Though it was in my mind, planning started quite late, a day before. I took opinion of my fellow colleagues; kerala, munnar, wayanad, tirupati, ooty. Finally decided on Coorg.
There was lot of information on net regarding Coorg, I decided for a homestay from http://www.homestaykodagu.com/home_stay.html and listed places to visit. We also wanted to see Mysore palace, so onward we went via Mysore.
After visiting the palace, we headed to Coorg; on way we visited Dubare water rafting, Raja Seat in Madikeri and Omkareswara temple. Later, as it was dark we went to our home stay in Kushalnagar. It was a pleasant stay. Sunday morning we went to Talacavery and Bagamandala. Afternoon at Abey waterfalls and had lunch at 4 at local home kind of hotel. Then in evening we went to Golden tample and back to bangalore at 1.00 AM. The trip was really fun and enjoying.
Monday, October 12, 2009 | By: Kunal Ekawde

Age Old Healing

Yoga!!, yes, surrendered to this age old science of healing.
And it works!!
I started practicing it for a week now and can feel the difference, my friend Aditya also helped me in suggesting different exercises.
And the appointment to doc, which i mentioned in my last blog -- canceled it.. :)
Monday, October 5, 2009 | By: Kunal Ekawde

Roller Coaster Life

Recovering from set of ailments, I've had it all.
Latest one being pain in neck or as doctors say as Cervical spondylits. Not exactly that, but its straight neck instead of curve, so got to do some exercises. Changed physio 2 times and again got to show to ortho.
It all began with an small particle which got caught up in my sole. After coming home from market, I felt the sensation in foot, so took a needle and tried to investigate, there was nothing. After a week i found, skin around it was becoming harder and a white dot and was a real pain in walking. So, i showed to doc and got a laser surgery done. Then it was 2 weeks of band-aid and popped some antibiotics. The wart infection didnt stop here, it cropped again and again showed to doc at Goa and took salicure treatment, aging there was pain then the doc here gave some pain killers. Those were really nice -- just for those 2 day and spoiled my 3 months and pain later. The pain killers triggered pain in stomach and caused gastritis. It got severe month later and had to do endoscopy, nothing major but had H pylori bacteria - which is common in Indians.
This pain in stomach also caused pulling pressure at chest and adding to it was severe headache because of neck pain. Alas till this point my wart infection was cured.

The doc gave me migraine pills after doing a CT scan -- which was normal. Still not satisfied i showed to ortho and was told the headache is due to neck and not because of migraine. So i stopped those pills and took again pain killer for neck pain which again triggered my stomach prob. Had sleepless night a lot times with uneasy feeling + stomach pain + neck pain + headache + giddiness. Again after a course of 10 day my stomach prob got resolved and again cropped up after i had 2 day chiken dishes followed by Mackerel curry. Now again its fine but had earache for last 2 days which now is reduced.

Finally, just one small particle changed my health for 3 months!!, currently almost fine but have to continue with exercise and consult ortho again after sometime.