ARTS Week 23

Algorithm

This week’s LeetCode problem is 50. Pow(x, n)

Implement pow(x, n), which calculates x raised to the power n (i.e., xn).

In order to use the dichotomy method, it is necessary to first ensure that n is always positive, so it is necessary to convert xn. First, judge n. If n < 0, the n-th power of x is equal to pow(1/x, -n). When n = 0 or 1, pow(x, n) is always x, only when n>1 , the nth power of x is to calculate pow(x,n). In the function calPow(double x, long n) that actually calculates xn, if n==0, it returns 1, and the result tmp of the xn/2 is obtained by recursion first, if n is Even, the final result is tmp*tmp; if n is odd, then the final result is tmp*tmp*x, the code is as follows:

Review

This week’s Review is for the following article: C Runtime Overhead

The author introduces what to do when the C language library (libc) becomes the bottleneck of program execution.

The author traced an empty program with strace -tt and found that it took up to 9.4ms between executions on his machine, which is entirely the overhead of the linker and the C language runtime

Then the author tries to use inline assembly and -ffreestanding -nostdlib to test the check:

It can be seen that this program without any system calls only runs for 0.5ms. Then the author tried to compile the program statically, and the running time was reduced to about 8ms. The output obtained from the trace is as follows:

Finally, the author wrote a minimal libc library to compile with the -ffreestanding -nostdlib flag, and the running time was reduced to 1ms, which is close to 1/ the running time of glibc 10, which has only five system calls:

Summary: If you feel that the program or process startup time is slow and really needs to be optimized from the library level, then it is worth your time to try another libc implementation (such as musl libc or Diet libc)

Tip

In the example of callback function in C language. the callback function is to treat one function as a parameter of another function. The most classic application is to customize the function of comparison size in the sorting algorithm. The following is a simple example, the operate function calls the add and multi functions to achieve the effect of addition and multiplication respectively.

The result of running the program is as follows:

Share

Now I have an idea about the topic of a non-ARTS technical blog post, which is roughly divided into three parts. I am currently working hard on writing, come on!

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
KeepNewbie_yan

KeepNewbie_yan

5 Followers

A programmer. Share knowledge of programming, operating system, Linux kernel, and reading, thinking etc. Let us maintain a beginner mend and grow together!