An Interesting C Program

#include <stdio.h>

int main()
{
    int i = 3;
    int j = 4;
    int *p = &j;
    *(p+1) = 7;
#if 1
    // addr &i is higher than &j 
    printf("%d, %d\n", i, j); // prints 7, 4
#else
    // addr &j is higher than &i
    printf("%d, %d\n%p, %p\n", i, j, &i, &j); // prints 3, 4
#endif
    return 0;
}

gdb a.out -batch -ex 'disassemble/s main'

Dump of assembler code for function main:
a.c:
4	{
   0x0000000000001169 <+0>:	endbr64 
   0x000000000000116d <+4>:	push   %rbp
   0x000000000000116e <+5>:	mov    %rsp,%rbp
   0x0000000000001171 <+8>:	sub    $0x20,%rsp
   0x0000000000001175 <+12>:	mov    %fs:0x28,%rax
   0x000000000000117e <+21>:	mov    %rax,-0x8(%rbp)
   0x0000000000001182 <+25>:	xor    %eax,%eax

5	    int i = 3;
   0x0000000000001184 <+27>:	movl   $0x3,-0x14(%rbp)

6	    int j = 4;
   0x000000000000118b <+34>:	movl   $0x4,-0x18(%rbp)

7	    int *p = &j;
   0x0000000000001192 <+41>:	lea    -0x18(%rbp),%rax
   0x0000000000001196 <+45>:	mov    %rax,-0x10(%rbp)

8	    *(p+1) = 7;
   0x000000000000119a <+49>:	mov    -0x10(%rbp),%rax
   0x000000000000119e <+53>:	add    $0x4,%rax
   0x00000000000011a2 <+57>:	movl   $0x7,(%rax)

9	#if 1
10	    // addr &i is higher than &j 
11	    printf("%d, %d\n", i, j); // prints 7, 4
   0x00000000000011a8 <+63>:	mov    -0x18(%rbp),%edx
   0x00000000000011ab <+66>:	mov    -0x14(%rbp),%eax
   0x00000000000011ae <+69>:	mov    %eax,%esi
   0x00000000000011b0 <+71>:	lea    0xe4d(%rip),%rdi        # 0x2004
   0x00000000000011b7 <+78>:	mov    $0x0,%eax
   0x00000000000011bc <+83>:	callq  0x1070 <printf@plt>

12	#else
13	    // addr &j is higher than &i
14	    printf("%d, %d\n%p, %p\n", i, j, &i, &j); // prints 3, 4
15	#endif
16	    return 0;
   0x00000000000011c1 <+88>:	mov    $0x0,%eax

17	}
   0x00000000000011c6 <+93>:	mov    -0x8(%rbp),%rcx
   0x00000000000011ca <+97>:	xor    %fs:0x28,%rcx
   0x00000000000011d3 <+106>:	je     0x11da <main+113>
   0x00000000000011d5 <+108>:	callq  0x1060 <__stack_chk_fail@plt>
   0x00000000000011da <+113>:	leaveq 
   0x00000000000011db <+114>:	retq   
End of assembler dump.
Dump of assembler code for function main:
a.c:
4	{
   0x0000000000001169 <+0>:	endbr64 
   0x000000000000116d <+4>:	push   %rbp
   0x000000000000116e <+5>:	mov    %rsp,%rbp
   0x0000000000001171 <+8>:	sub    $0x20,%rsp
   0x0000000000001175 <+12>:	mov    %fs:0x28,%rax
   0x000000000000117e <+21>:	mov    %rax,-0x8(%rbp)
   0x0000000000001182 <+25>:	xor    %eax,%eax

5	    int i = 3;
   0x0000000000001184 <+27>:	movl   $0x3,-0x18(%rbp)

6	    int j = 4;
   0x000000000000118b <+34>:	movl   $0x4,-0x14(%rbp)

7	    int *p = &j;
   0x0000000000001192 <+41>:	lea    -0x14(%rbp),%rax
   0x0000000000001196 <+45>:	mov    %rax,-0x10(%rbp)

8	    *(p+1) = 7;
   0x000000000000119a <+49>:	mov    -0x10(%rbp),%rax
   0x000000000000119e <+53>:	add    $0x4,%rax
   0x00000000000011a2 <+57>:	movl   $0x7,(%rax)

9	#if 0
10	    // addr &i is higher than &j 
11	    printf("%d, %d\n", i, j); // prints 7, 4
12	#else
13	    // addr &j is higher than &i
14	    printf("%d, %d\n%p, %p\n", i, j, &i, &j); // prints 3, 4
   0x00000000000011a8 <+63>:	mov    -0x14(%rbp),%edx
   0x00000000000011ab <+66>:	mov    -0x18(%rbp),%eax
   0x00000000000011ae <+69>:	lea    -0x14(%rbp),%rsi
   0x00000000000011b2 <+73>:	lea    -0x18(%rbp),%rcx
   0x00000000000011b6 <+77>:	mov    %rsi,%r8
   0x00000000000011b9 <+80>:	mov    %eax,%esi
   0x00000000000011bb <+82>:	lea    0xe42(%rip),%rdi        # 0x2004
   0x00000000000011c2 <+89>:	mov    $0x0,%eax
   0x00000000000011c7 <+94>:	callq  0x1070 <printf@plt>

15	#endif
16	    return 0;
   0x00000000000011cc <+99>:	mov    $0x0,%eax

17	}
   0x00000000000011d1 <+104>:	mov    -0x8(%rbp),%rdi
   0x00000000000011d5 <+108>:	xor    %fs:0x28,%rdi
   0x00000000000011de <+117>:	je     0x11e5 <main+124>
   0x00000000000011e0 <+119>:	callq  0x1060 <__stack_chk_fail@plt>
   0x00000000000011e5 <+124>:	leaveq 
   0x00000000000011e6 <+125>:	retq   
End of assembler dump.

Getting older, huh?

Getting older, huh? I have experienced some things that were extraordinarily meaningful in the year 2020: I started to write academic papers in English, pursuing perfectly-typeset articles and I have done some results that I’m now still very proud of. I started to browse English websites every day, hankering for an ideal & beautiful country to live in and work in. I went to see the sea for the first time on June 3, 2020, with my roomie Wang Yichuan, with whom I had a few conflicts but also indelible time together doing mathematical modeling and cooking. I started to notice that I was really a jerk and I had done a few unkind things which I took for granted, I wished to go to the church and confess my sins. I became more sensitive, sweet, and understanding. I found my goal again which is to continue my studies as I really enjoyed a lot the whole process when I was doing rigorous research. I never have had so strong a desire to study, and I wish to go to Germany to pursue my academic career!

Why Write a Thesis?

(I found some very insightful and enlightening words about why we should write a thesis.)

The answer “Because it’s required” is not good enough. In fact, the question “Why write a thesis?” is itself misleading, because it implies that what’s most important is the final product: an object that you will print out on acid-free paper, pinch into a spring binder, and hand in.

The more useful question is, “What am I going to get out of this experience?” This question foregrounds the fact that thesis-writing is a process, and that the purpose of that process is not only to produce a great thesis, but even more importantly, to transform you into a better writer, researcher, and most of all, thinker.

As you envision, research, structure, write, and rewrite your thesis, you will encounter complex and important questions, grapple with unwieldy and sometimes overwhelming data, listen in new ways to ongoing
scholarly conversations, confront challenging intellectual puzzles, and struggle to form and articulate your own thoughts. These trials will change you. If you trust and commit to the process, you will emerge at the end of your senior year with new skills and a better sense of your own voice. And as a more powerful writer and thinker, you will be more effective in all your post-graduation pursuits.

In order to achieve the most important goal of self-transformation, a student must aim, paradoxically, for another goal: creating new scholarly knowledge. Imagine that you are trying to spear a fish in a pond.
If you aim your spear at the spot where you see the fish, you will miss, because the surface of the water refracts light. Similarly, if you aim only to transform yourself into a better writer, researcher, and thinker,
you will miss both that goal and the goal of producing high-quality scholarship. You must endeavor, with every ounce of intelligence and strength you have, to produce an original and valuable academic
argument. As you do so, you will transform—inevitably. Aim for the tangible goal of writing a superb thesis, and you will reach the more important but elusive objective beyond it.

The process of writing a thesis can be a glorious adventure. I hope that you will experience the exhilaration of watching your ideas emerge, the astonishment of discovering newly developed abilities, and the satisfaction of completing an arduous but important journey. Now is the time to take your first step.

–Robin Bernstein, Assistant Professor of Women, Gender, and Sexuality and of History and Literature

Memory & CPU Caches

This week and last weekend I was primarily focusing on memory pools, allocators, CPU caches. I now probably know how allocators work, simply separating memory allocation & objects initialization, for example, reserve() function in std::vector, it doesn’t initialize the allocated data segment, thus permitting better performance when we don’t need initialize the data immediately.

CPU cache is another very interesting & important aspect that can (hugely) influence the performance of our programs, as it’s way faster than main memory (RAM). Smaller is faster. A great resource I found on Tuesday evening was a YouTube video – Scott Meyers’s presentation on code::drive conference 2014, a very humorous & high-quality speech!! Really awesome!

Here are a few slides screenshots, the complete presentation pdf version can be downloaded from here.

There are some interesting tops contained within it: cache lines, false sharing, data-oriented design, etc. Very practical and constructive.

From Wednesday and later, I reviewed my qsort vs std::sort problem in terms of cpu cache and cache lines. I found a hug bug (typo) in my qsort function call (embarrassed). Then I further developed that, added a few more tests (for instance, indirect sort), and drew some charts. The details can be found here.


Supplemented on Nov 24, 2020

About cache associativity: see https://www.youtube.com/watch?v=UCK-0fCchmY, a very detailed & intuitive demonstration.

Additional resource: Gallery of Processor Cache Effects by Igor Ostrovsky.