One simple way to get object size

1
2
3
4
5
6
7

<dependency>
    <groupId>com.carrotsearch</groupId>
    <artifactId>java-sizeof</artifactId>
    <version>0.0.5</version>
</dependency>

System.out.println(RamUsageEstimator.sizeOf(new String("hello world!")));

what kind of occasion we need to deal with

consider code behind.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

public void A() throws InterruptedException {
		for(int i = 0; i < 50; i ++) {
			Thread thread = new Thread(new Runnable() {							
				@Override
				public void run() {
					for(int i = 0; i < 2; i++) {						
						++ number;
						System.out.println(Thread.currentThread().getName() + " get " + number);					
					}											
				}
			});
			thread.start();
		}
		Thread.sleep(3000);
		System.out.println("finally " + number);
	}

finally, the result of ‘number’ is not predictable, which might be 960, 977 or 999.

what volatile can guarantee

it keeps every thread get ‘global’ variable with consitent value. one more thing, ++number is not atomic, update number in multi-thread is not safe. add synchronized symbol will make it.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

public void A() throws InterruptedException {
		for(int i = 0; i < 50; i ++) {
			Thread thread = new Thread(new Runnable() {							
				@Override
				public void run() {
					for(int i = 0; i < 2; i++) {
						synchronized (integerLock) {
							++ number;
							System.out.println(Thread.currentThread().getName() + " get " + number);
						}											
					}											
				}
			});
			thread.start();
		}
		Thread.sleep(3000);
		System.out.println("finally " + number);
	}

so, synchronized can be a useable way in this occasion. compared to Optimistic Lock, synchronized cost too much, as it is a kind of Pessimistic Lock.

what volatile means

n. a volatile substance; a substance that changes readily from solid or liquid to a vapor, which means somthing can be changed at anytime.

As statement ‘lock’ will have bus or cache(cpu level) all to itself(core), which will influence multi-core performance. cas + volatile is a kind of Optimistic Lock, code follows.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103

/**
 * @ClassName:     CASTest.java
 * @Description:   TODO
 * 
 * @author
         xiang_wang

 * @version
        V1.0  
 * @Date           2018年10月25日 下午3:13:08 
 */
import java.lang.reflect.Field;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;


import sun.misc.Unsafe;

/**
 * @author xiang_wang
 *
 */
public class CASTest {
	private volatile int value = 0;
	
	public int get() {
		return value;
		
	}
	
	public int increaseAndGet() throws NoSuchFieldException, SecurityException, InterruptedException {
		while(true) {
			int next = value + 1;
			if(innerCas(value, next)) {
				return next;
			}else {
				System.out.println(Thread.currentThread().getName() + " wait.");
				Thread.sleep(100);
			}
		}
	}
	
	private boolean innerCas(int before, int after) throws NoSuchFieldException, SecurityException {
		Unsafe unsafe = getUnsafe();
		return unsafe.compareAndSwapInt(this, unsafe.objectFieldOffset(CASTest.class.getDeclaredField("value")), before, after);
	}
	
	public static Unsafe getUnsafe() {
        try {
            Field singletonInstanceField = Unsafe.class.getDeclaredField("theUnsafe");
            singletonInstanceField.setAccessible(true);
            return (Unsafe) singletonInstanceField.get(null);
        } catch (NoSuchFieldException e) {
            e.printStackTrace();
        } catch (IllegalAccessException e) {
            e.printStackTrace();
        }
        return null;
    }

	/** 
	 * @Title:        main 
	 * @Description:  TODO 
	 * @param:        @param args    
	 * @return:       void    
	 * @throws 
	 * @author        xiang_wang
	 * @Date          2018年10月25日 下午3:13:09 
	 * @throws SecurityException 
	 * @throws NoSuchFieldException 
	 * @throws InterruptedException 
	*/
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		CASTest casTest = new CASTest();		
		ExecutorService es = Executors.newFixedThreadPool(10);
		for(int i = 0; i < 10; ++ i) {
			es.execute(new Runnable() {
				
				@Override
				public void run() {
					
					try {
						while(true) {
							System.out.println(Thread.currentThread().getName() + ":" + casTest.increaseAndGet());
							Thread.sleep(100);
						}					
					} catch (NoSuchFieldException e) {
						// TODO Auto-generated catch block
						e.printStackTrace();
					} catch (SecurityException e) {
						// TODO Auto-generated catch block
						e.printStackTrace();
					} catch (InterruptedException e) {
						// TODO Auto-generated catch block
						e.printStackTrace();
					}				
				}
			});
		}		
	}

}

Conclusion, the method is reliable. but I am more interested in the parameters in this program. ‘Thread.sleep(100)’ statement may influence program performance, At least that’s what I believed when I wrote the program.
let’s test it. In my opinion, the first statement will make increaseAndGet faster and the second will make thread competition more fiercely.

when interval of retry time decrease, and competition between threads, repetition will occur, as value may have been revised by other threads.
consider this two statements:

1
2

int next = value + 1;	// statement 1
if(innerCas(value, next)) {	// statement 2

1. In thread-1, value is 10, after statement 1, next is 11
2. In thread-2, value changes from 10 to 11.
3. In thread-1, statement 2 executes, value = 11, next = 11, uhuhuh

fix bug:

1
2
3
4
5
6

int before = value;	// save value for thread-x
int next = before + 1; // save update value to thread-x
if(innerCas(before, next)) {
	return next;
}else {
xxx

experiment result and analysis:

when wait time is as short as possible, retry time influence conflict time significantly. the lower retry time is, the more times thread try to update ‘value’.
when wait time is long enough, the times become reverse related. retry and wait range from 50 to 1000 has no significant effect to total execution time, which is main related to wait time.

慢开始算法：当主机开始发送数据时，如果立即所大量数据字节注入到网络，那么就有可能引起网络拥塞，因为现在并不清楚网络的负荷情况。因此，较好的方法是 先探测一下，即由小到大逐渐增大发送窗口，也就是说，由小到大逐渐增大拥塞窗口数值。通常在刚刚开始发送报文段时，先把拥塞窗口 cwnd 设置为一个最大报文段MSS的数值。而在每收到一个对新的报文段的确认后，把拥塞窗口增加至多一个MSS的数值。用这样的方法逐步增大发送方的拥塞窗口 cwnd ，可以使分组注入到网络的速率更加合理。
每经过一个传输轮次，拥塞窗口 cwnd 就加倍。一个传输轮次所经历的时间其实就是往返时间RTT。不过“传输轮次”更加强调：把拥塞窗口cwnd所允许发送的报文段都连续发送出去，并收到了对已发送的最后一个字节的确认。
另，慢开始的“慢”并不是指cwnd的增长速率慢，而是指在TCP开始发送报文段时先设置cwnd=1，使得发送方在开始时只发送一个报文段（目的是试探一下网络的拥塞情况），然后再逐渐增大cwnd。
为了防止拥塞窗口cwnd增长过大引起网络拥塞，还需要设置一个慢开始门限ssthresh状态变量（如何设置ssthresh）。慢开始门限ssthresh的用法如下：
当 cwnd < ssthresh 时，使用上述的慢开始算法。
当 cwnd > ssthresh 时，停止使用慢开始算法而改用拥塞避免算法。
当 cwnd = ssthresh 时，既可使用慢开始算法，也可使用拥塞控制避免算法。
拥塞避免算法：让拥塞窗口cwnd缓慢地增大，即每经过一个往返时间RTT就把发送方的拥塞窗口cwnd加1，而不是加倍。这样拥塞窗口cwnd按线性规律缓慢增长，比慢开始算法的拥塞窗口增长速率缓慢得多。

与快重传配合使用的还有快恢复算法，其过程有以下两个要点：

<1>. 当发送方连续收到三个重复确认，就执行“乘法减小”算法，把慢开始门限ssthresh减半。这是为了预防网络发生拥塞。请注意：接下去不执行慢开始算法。

<2>. 由于发送方现在认为网络很可能没有发生拥塞，因此与慢开始不同之处是现在不执行慢开始算法（即拥塞窗口cwnd现在不设置为1），而是把cwnd值设置为 慢开始门限ssthresh减半后的数值，然后开始执行拥塞避免算法（“加法增大”），使拥塞窗口缓慢地线性增大。

###Substr finding algorithm : Sunday

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

 int sunday(char SArrary[], int iSLen, char TArrary[], int iTLen)
{
	int i = 0, j = 0, pos = -1;
	while (i < iSLen)
	{
		if (SArrary[i] == TArrary[j])
		{
			++i;
			++j;
			if (j == iTLen - 1)
			{
				pos = i - j;
			}
		}
		else
		{
			// 下一个需要比较的字符串位置next
			int next = iTLen - j + i;
			int k = iTLen - 1;
			for (; k >= 0; --k)
			{
				if (SArrary[next] == TArrary[k])
				{
					break;
				}
			}
			//找到对应的字符
			if (k >= 0)
			{
				// i的新下标位置
				i = next - k;
			}
			else
			{
				++i;
			}
			j = 0;
		}
	}

	return pos;
}

Process_Communication

###Permuation with Lua code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

function print_arr(dataArr, length)
	local str = "";
	for i = 1, length do
		str = str.."\t"..tostring(dataArr[i]);
	end
	print(str)
end

function swap(data, i, index)
	t = data[index];
	data[index] = data[i];
	data[i] = t;
end

function permutation(data, sbegin, send)
	if sbegin == send then
		print_arr(data, 4);
		return;
	end

	for i = sbegin, send do
		swap(data, sbegin, i);
		permutation(data, sbegin + 1, send);
		swap(data, sbegin, i);
	end
end

data = {1, 2, 3, 4};
permutation(data, 1, 4);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

void swap(char *a, char *b){
	char temp = *a;
	*a = *b;
	*b = temp;
	temp = *a;
}

void print_arr(string str){
	for (string::iterator it = str.begin(); it != str.end(); ++it){
			cout << *it << '\t';
		}
		cout << endl;
}

void permutation(string str, int begin, int end){
	if (begin == end){
		print_arr(str);
	}

	for (int i = begin; i < str.length(); ++i){
		swap(&str[begin], &str[i]);
		permutation(str, begin + 1, end);
		swap(&str[begin], &str[i]);
	}
}

int main(){
	string str("abc");
	permutation(str, 0, str.length() - 1);
	return 0;
}

#Memory-layout-of-variable-in-C-program

1. As you know, variable in C can be classified info local variable, global variable. Local variable is stored in Stack, memory allocated with malloc/alloc locates in Heap. Global variable and Static Variable is located in global data area, which consists of DS and BSS. DS (data segment) contains initialized variable, which is not zero. DS can be divided into readonly DS area and read write DS area. BSS (block started by symbol) contains uninitialized variable or variable initialized with zero, which can also be divied into readonly BSS area and read write area.

2.Sample

void ppp(int parameter) {

return;

}

int main() {
ppp(12);
return 0;
}

REG BEGIN PUSH EBP MOV EBP, ESP
EBP 0036FD88 0036FD88 0036FD74 main in
ESP 0036FD78 0036FD74 0036FD74

REG BEGIN PUSH EBP MOV EBP, ESP
EBP 0036FD74 0036FD74 0036FC9C ppp in
ESP 0036FCA0 0036FC9C 0036FC9C

REG BEGIN MOV ESP, EBP POP EBP
EBP 0036FC9C 0036FC9C 0036FD74 ppp return
ESP 0036F9D0 0036FC9C 0036FCA0

REG BEGIN MOV ESP, EBP POP EBP
EBP 0036FD74 0036FD74 0036FD88 main return
ESP 0036FD74 0036FD74 0036FD78

Before the program enter main procudure, EBP is 0x0036FD88, so this is the Base Address of current Call Frame, ESP is bigger than EBP, I think all of us can undersand this in X86 Cpu architecture. Now, we enter main, I think I should save the Base Address, right now. As we know, Context should be saved and recovered when key operations begins and stops. So 0x0036FD88 is save to stack, then ESP is decreased to 0x0036FD74. And the same time, EBP is decreased to ESP (0x0036FD84).

####Link Reverse

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

Node * reverse_link(Node *cur){
	if(cur == NULL){
		return cur;
	}

	if(cur->next == NULL){
		return cur;
	}

	Node *tmp = reverse_link(cur->next);
	cur->next->next = cur;
	cur->next = NULL;
	return tmp;
}

Node * reverse_link_loop(Node *cur){
	Node *pre = NULL;
	Node *next= NULL;

	while(cur){
		next = cur->next;
		cur->next = pre;
		pre = cur;
		cur = next;
	}
	return pre;
}

###LCS Problem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

int getLcs(string a, string b) {
	int lengthA = a.length() + 1, lengthB = b.length() + 1;
	vector<vector<char> > matrix;
	matrix.resize((lengthA));
	for (int i = 0; i < lengthA; ++i) {
		matrix[i].resize(lengthB);
	}	
	int max_pos = -1, max_val = -1;
	for (int i = 1; i < lengthA; ++i) {
		for (int j = 1; j < lengthB; ++j) {
			if (a[i - 1] == b[j - 1]) {
				matrix[i][j] = matrix[i - 1][j - 1] + 1;
				if (max_val < matrix[i][j]) {
					max_val = matrix[i][j];
					max_pos = i;
				}
			}
			else 
			{
				matrix[i][j] = max(matrix[i - 1][j], matrix[i][j - 1]);
			}
		}
	}
	
	return max_pos;
}

Generally, we use operator ++ to increase variable, especially in loop.
raw datatype situation

We can using ++i and i++ equally. Translating the two command into assembly language, firstly i++, a = i++;

1
2
3
4
5
6
7
8
9
10
11
12
13

00B61AC3  mov         eax,dword ptr [i]  
00B61AC6  mov         dword ptr [a],eax  
00B61AC9  mov         ecx,dword ptr [i]  
00B61ACC  add         ecx,1  
00B61ACF  mov         dword ptr [i],ecx
++i can be expressed as follow, b = ++i;  

00B61AD2  mov         eax,dword ptr [i]  
00B61AD5  add         eax,1  
00B61AD8  mov         dword ptr [i],eax  
00B61ADB  mov         ecx,dword ptr [i]  
00B61ADE  mov         dword ptr [b],ecx

Obviously, they cost time equally.

Now, we consider the other situation.
user-defined datatype situation

Considering class INTEGER,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

template <class T>
class INTEGER{
	T value;
	public:
		INTEGER(T intVal){
			value = intVal;
		}
		INTEGER(){
			value = 1;
		}
		INTEGER& operator ++(){
			value += 1;
			return *this;
		}
		INTEGER operator ++(int){
			INTEGER tempInteger(value);
			value ++;
			return tempInteger;
		}
		void print_val(){
			cout << hex << "0x" << value << endl;
		}
};