Pages

Wednesday, December 30, 2015

Built-in Smart Pointers in Modern C++

C++ is a general programming language that supports raw pointers. To use the raw pointers, we have to manage the memory carefully with new/delete, new[]/delete[], or perhaps C-style malloc/free pairs. The memory leak is always a potential risk -- imagine a runtime_error just occurred. Detecting tools like Valgrind or Garbage Collectors like Boehm GC[using mark-sweep algorithm] may be helpful to some extent, but it's still our responsibilities to make sure that the memory is properly managed and thus less time is left for the actual business needs.

Smart pointer is one answer in the language level. Actually, smart pointers were introduced in C++98. With the move semantics, they got even better in C+11.

Topics in C++ built-in smart pointers could be intricate if we dig them further deep into areas, such as GC algorithms, thread safety and exception safety. In this post, I'll compare the various smart pointers in a high level, and summarize it in a simple table. For the detailed discussion and the guidelines to use them, please refer to Chapter 4 of Scott Meyers' "Effective Modern C++", or <memory> on cplusplus.com.


raw pointer
auto_ptr
unique_ptr
shared_ptr
weak_ptr
Language support
Always allowed
Deprecated in C++11
C++11 (replacing auto_ptr)
C++11
C++11
What are they
T* t
T *t[n]

Wrapper of raw pointer
·   A smart ptr uniquely owned -- no two unique_ptr instances manage one object
·   It provides a limited GC
·   It contains a stored ptr and a stored deleter.
 .  Move-only type.
·  A smart ptr shared ownership group
·   It contains a stored ptr and an owned ptr to control block.
·  Stored and owned ptrs may refer to one object.
·   Empty shared_ptr
·   Null shared_ptr
·  A smart ptr holding non-owning ref. to an object managed by shared_ptr.
·   It models the temp ownership


Use Cases
Almost never in practice
Prefer to unique_ptr
 .  A ptr w/ exclusive ownership.
 .  Used in Pimpl idiom
 .  A ptr w/ shared ownership.
 .  A shared_ptr like ptr in risk of dangling.

How to use
new/delete
new[]/delete[]


up = make_unique<T>();//C++14
up = make_unique<T[]>();
up.get_deleter();
T* rp = up.get();
T* rp = up.release();
up.reset(p);//destroy & own p
*up
up->v1
shared_ptr<T> up{move(up)};
sp = make_shared<T>(n);
sp = make_shared<T[]>(n);
sp.use_count()
sp.unique()?
T* rp = sp.get(); // stored ptr
sp.reset();
*sp
sp->v1
sp1=allocate_shared<T>(alloc,10);
weak_ptr<T> wp(sp);
sp1=wp.lock()
wp.use_count()
wp.expired()?
wp.reset();

Pros


·   Small and fast. Little overhead over raw pointer.
·  Easy to convert to shared_ptr
 . Allowed to custom deleter (using lambda expression)
 . Capture closure support
 . Low overhead (2 x unique_ptr)
 . Works in multi-threaded 
       environments.
 .  Prevent shared_ptr cycles.
 .  shared_ptr <==> weak_ptr
Cons


·  Not capoyable
 .  Circular reference
 .  Exception: bad_weak_ptr



"The present is the past rolled up for action, and the past is the present unrolled for understanding." - Will Durant. 

REPL, Online IDE and Tools for Static Code Analysis

The code in general programming languages like Java and C++ and code is usually compiled and tested in IDEs. In other scripting languages, it's common to see a REPL (read-eval-print loop) language shell -- interactive interpreter.

REPL environment allows us to run the code piece by piece. This is very handy for testing purpose sometimes. Now there are some solutions in Java and C++.
[My thinking of picking a pair of similar tools comes from Hotelling's law -- "Linear City Model", though many more other tools are available, too.]

1. cint and igcc are two REPL simulators for C/C++.
2. javarepl and Eclipse's "scrap book" are two REPL simulators for Java.
3. ideone, codechef, and coding-ground provide online compiler suites for various programming languages(C++, Java, Scala, R, Python) by using cloud computing technologies.
4. cppcheck and cpplint.py are two tools for C++ static code analysis.

Coding ground is my favorite. It supports almost all popular languages, and claims 100% cloud. Best of all, it displays the command line and allows me to change the compiling options!

* As of December 2015, coding ground works well on my PC. It has an Android app for Tutorialspoint, but it's slow and Coding Ground on my Galaxy Note 4 is not working as well as it is on PCs.

Monday, December 28, 2015

Move Semantics and Constructors

C++11 includes four types of constructors:
  1. Default Constructor
  2. Conversion Constructor (disabled if explicit)
  3. Copy Constructor (const &)
  4. Move Constructor (&&)
C++11 also allows two types of assignment operators:
  1. (Copy) Assignment Operator (const &)
  2. Move Assignment Operator (&&)
The following is the sample code to demonstrate what they look like:

// MyCPP11Container.cpp

template<typename T, int value>
class MyCPP11Container
{
public:
 MyCPP11Container() {                                  // 1. DEFAULT CTOR
  /*intended to be empty*/
 }
 explicit MyCPP11Container(int) : MyCPP11Container() {  // 2. Disable CONVERSION CTOR
                            // DELEGATE CONSTRUCTION
  m_pData = new T(value);
 }
 MyCPP11Container(const MyCPP11Container& other) : m_pData(NULL) { // 3. COPY CTOR
  *this = other;
 }
 MyCPP11Container(MyCPP11Container&& other) : m_pData(NULL) {      // 4. MOVE CTOR
  *this = std::move(other);
 }
 virtual ~MyCPP11Container() { // DESTRUCTOR
                if (m_pData != NULL) {
      delete m_pData;
                }
 }

 MyCPP11Container& operator=(const MyCPP11Container& other) { // ASSIGNMENT OPTR
  if (this == &other) {
   return *this;
  }
  delete m_pData;
  m_pData = new int(*(other.m_pData));
 }

 MyCPP11Container& operator=(MyCPP11Container&& other) {      // MOVE ASSIGNMENT OPTR
  if (this == &other) {
   return *this;
  }
  delete m_pData;
  m_pData = other.m_pData;
  other.m_Ptr = nullptr; // So the destructor doesn't free memory multiple times.
 }

 operator T() const { return *m_pData; } // type conversion: (T).

private:
 T* m_pData;
};


// C++11 version of swap in <utility> behaves like this:

template <class T> void swap (T& a, T& b) {                 // moved in <utility>
  T c(std::move(a)); a=std::move(b); b=std::move(c);
}

Note that swap() has been in <algorithm> until C++11. std::move() in <utility> is the new semantic move, which is different from the ranged std::move() in <algorithm>.

typename remove_reference<T>::type&& move (T&& arg) noexcept;  // <utility>



Parallel Programming Paradigms - MPI, OpenMP and CUDA


MPI
OpenMP
CUDA
Description

Multi-threaded API
Parallel Computing Platform
and API (NVIDIA GPU)
Compiler
mpicc
gcc –fompenmp -Igomp
nvcc (LLVM-based)
Headers
#include <mpi.h>
#include <omp.h>
#include <cuda_runtime.h>
CFlags
-I/usr/lib/openmpi
-L/usr/lib/openmpi/…/lib
-lmpi
lgomp
-I/usr/local/cuda/include
-L/usr/local/cuda/lib
-lcudrt
Memory Model
Shared memory and Distributed memory
Shared memory multiprocessing
Shared memory
Concepts
Point-to-point messaging
Broadcasting (1 to M)
Scatter/Gather. Support R, C++, Java, Fortran, Python.
An add-on in compiler
Designed to work with C/C++ and Fortran. More effective for parallel computing: e.g., fast sort algorithms of large lists.
Variates
OpenMPI, MPICH2

SIMD, SIMT, SMT
Pros
More general solution;
Can run in clustering environments;
Distributed memory is less expensive
Easier to program;
Can still run the program as a serial code(no code change);

Scattered reads;
Unified virtual memory;
Fast shared memory;
Full support for integer and bitwise operations.
Cons
Code change from serial to parallel version;
Harder to debug;
Bottleneck of network communication.
Difficult to debug synchronization bugs and race conditions;
Requires compiler support;
Only in shared memory architecture;
Mostly used in loop parallelization.
Memory copy between host and device may incur performance hit due to bandwidth and latency;
Thread group with 32+ threads for best performance;
Valid C/C++ may not compile;
C++ RTTI is not support(?).

The information sources in the above table include, but not limited to, open-mpi.org, openmp.org, nvidia.com and Wikipedia.org.

Saturday, December 26, 2015

Eclipse CDT, a C++ IDEs on Windows

In addition to VC++, a few open sourced C++ IDEs are also widely used on Windows: Code::Block and Eclipse CDT.

Eclipse CDT is available in Eclipse IDE for C++ Developers or as a plugin in Eclipse. Here is how to set up Eclipse CDT for C++11.
  • Install New Software... in Eclipse IDE for Java Developers            
        (web url: http://download.eclipse.org/tools/cdt/releases/8.8)
  • Install a C++ Compiler (e.g., Cygwin including g++ and make)
  • Create New C++ Project
  • In C/C++ Build > Settings > Other Flags Box, append "-std=c++11"
The following is the screenshot of my Eclipse 


Note: RAND_MAX is a macro defined in <cstdlib>. RAND_MAX = 32,767 in VC++, while RAND_MAX = 2,147,483,647 in GNU g++.

C++ 11 New Feature List (for Quants)

This is a list of C++ 11 (https://isocpp.org/wiki/faq/cpp11) new features (relative to C++98):
  • RValue Reference and move ctor.
  • Lambda Expression (for functional programming)
  • Concurrency API (future, async)
  • New Smart Pointers (unique_ptr, shared_ptr in <memory>)
  • Fixed-length <array>
  • <random> supports Mersenne Twister(MT19937) PRNG and distributions.
  • Enhanced Containers: <forward_list> and hashed <unordered_map>
  • Compile-time static_assert with <type_traits> for template code
  • noexcept, unexpected() and the enhanced <exception>
  • <regex> with EMCAScript syntax and backreference
  • RTTI: auto, decltype, and typeid 
  • Misc (ranged for loop, nullptr, non-type template parameters)

C++ Standard Library(since C++98), which is based on STL (designed and developed by Alexander Stepanov and Meng Lee), contains key components called containers, algorithms, functional and iterators.

Here the discussion is focused on Iterator, since it is very relevant to the performance. As shown in the following graph, C++/STL has 5-category iterators. Another way to present the iterator hierarchical relationship is using UML class diagram, with Input/Output as the bases at the top and Random Access Iterator at the bottom. A rule of thumb for choosing the iterators is to pick the weakest iterator first to accommodate the most efficient algorithm.

For example,
Forward Iterator: std::replace()
Bidirectional Iterator: std::reverse()
Random Access Iterator: std::sort()

Just for fun, I collected some C++ and OOP buzzwords and put them in a table.

RAII
Resource Acquisition Is Initialization
CADR
CTOR Acquire, DTOR Release, scoped-based res mgmt
RTTI
RunTime Type Info
BSS
Block Started by Symbol. Memory Layout: Stack, [Free Memory], Heap, Initialized Data, BSS, Text.
vtable
Virtual function Table
STL
3-legged STooL: Algorithm, Iterator, Containers
Algorithms
Algorithms use iterators and containers
Iterator Types
Input/Output, Forward, Bidirectional, Random Access
Container Types
Sequential, Associative. <forward_list>, <unordered_map>
Smart Pointer
Various raw pointer wrappers in <memory>
Pragma once
Directives similar to Include Guard
ADL
Argument-dependent lookup, Koenig Lookup
Move Semantics
Most pervasive C++11 feature. Move CTOR,  Move Assignment Operator for perf. Perfect Forwarding?
Move CTOR
Move Constructor
Rvalue Reference
<utility>
Boost
Open Source Library, some added in C++11/14.
Empty Aggregate Initialization
Could be very tricky.
Non-type Template Parameters
Enhanced template.
Exception-Safety
Basic and Strong exception safety. noexcept, throw, try-catch, unexpected() in <exception>. logic_error, runtime_error in <stdexcept>
Thread-Safety
<thread>, <future>. async(), future.get(), timeout.
volatile for hardware access, std::atomic for MT.
<random>
RAND_MAX? Platform-indep? Various Probability Distributions.
assert vs static_assert
#define NDEBUG vs compile-time assert. <type_traits>
OOP Key Concepts
Encapsulation, Inheritance, Polymorphism
SOLID
Single-responsibility, Open for extension/Closed for modification, Liskov substitution, Interface segregation, Dependency inversion.
LLVM
Low Level Virtual Machine, Clang compiler
JIT vs AOT
Just-in-time(CPU cycle stealing) vs Ahead-of-time Compilation
SIMD
Single Instruction, Multiple Data -- Flynn's Taxonomy. Intel MMX, SSE, AVX. 64bit CPU has 16 GPRs.
Hi-C Lo-C
High Cohesion, Low Coupling
GoF
Gang of Four, author of “Design Patterns”
IoC
Inversion of Control. Dep. Inj. Implements IoC for resolving dependency. No need to create the object by yourself. Template Method is another IoC example.
Pimpl
(Opaque-pointer)
Pointer to IMPLementation, Compiler firewall idiom, Handle class, “Cheshire Cat”.
Forward Declaration
Reduce build time


"... as you learned more [C++11], you were surprised by the scope of the changes. auto declarations, range-based for loops, lambda expressions, and rvalue references change the face of C++, to say nothing of the new concurrency features. And then there are the idiomatic changes. NULL(0) and typedefs are out, nullptr and alias declarations are in. enums should now be scoped. Smart pointers are now preferable to built-in ones. Moving objects is normally better than copying them."
  -- 
Scott Meyers, in 
"Effective Modern C++" 2015.

Friday, December 25, 2015

Java Native Interface

JNI supports two way interaction between Java and other languages, such as C++, C, Assembly.


Here I describe how to use JNI for Java/C++ 2-way Calls:
 1) Create a Java Project with MyExample.java with native methods.
     run "javah -jni MyExample" to generate MyExample.h

 2) Create a C++ DLL Project with MyDLL.cpp(#include "MyExample.h")
     In Project Properties, add Additional Include Directories:
            C:\Java\jdk1.7.0_79\include\win32;C:\Java\jdk1.7.0_79\include

 3) In Java project, add MyDLL.dll to Native Library Location.
     In Java code, add System.loadLibrary("MyDLL");


Note: A common run-time error when using JNI is java.lang.UnsatisfiedLinkError, which may be caused by 32-bit/64-bit DLL version mismatch or function signature mismatch. Here is a few tips to deal with this issue.
  • 64-bit JDKs usually work with 64-bit DLLs, while 32-bit JDKs work with 32-bit DLLs.
    Although java provides options -d32 or -d64, it's not always working.
  • To check if a DLL is a 32-bit, run "vcvarsall.bat amd64" and
    "dumpbin.exe \headers MyDLL.dll" 
  • One code base can support both 32-bit and 64-bit platforms.
The tools used in the above discussion: Java 1.7+, Eclipse(Mars) for Java, VC++(2013) for C++.

For best practice of using JNI, I recommend one article on IBM website: "Techniques and tools for averting the 10 most common JNI programming mistakes".

Note: Java is newer than C++, but they are influencing each other since the beginning. Wikipedia provides an excellent comparison of the big two, here is the link.

Thursday, December 24, 2015

QuantLib

1, QuantLib can be built with VC++ 2013, as instructed at http://quantlib.org/install/vc10.shtml

2, QuantLib is a well-designed C++ library and ported to R and Python.
    Check out the training material at http://www.implementingquantlib.com/p/training.html

3, Serious about QuantLib? Get a copy of <<Implementing QuantLib>> written by Luigi Ballabio.

4, Quick view of Class Hierarchy: http://yetanotherquant.de/QuantLib/book/BookQuantLib.pdf





Monday, December 21, 2015

Fun with Linux

1) Remove ^M
    $vi file.txt
    >:%s/^V^M//g

2) 64 bit or 32 bit?
    $uname -a
    $lscpu
    $more /proc/cpuinfo
    $nproc

3) Copy and preserving the same mode including timestamp
    $cp -p a.txt b.txt
    $cp -a a b

4) Who logged, from where?
    $w
    $last myuserid

5) Compiling C++ code?
    $g++ -shared ...
    $g++ -static-libgcc -L. -o hello hello.cpp
    $ar mylib.a mylib.o

6) Sort in reverse order (find, grep,...)
    $sort -r file.txt

7) To show free, total, and swap memory info in bytes
    $free -t

8) List top processes?
    $top -u myuserid

9) Backup or transfer files?
    $tar cvf a.tar /subdir
    $tar xvf a.tar

10) List all open files?
    $lsof -u myuserid

Sunday, December 13, 2015

Month-End Time Series vs Monthly Candle Chart

library(quantmod)
getSymbols("WMT")
wmt = do.call(rbind, lapply(split(WMT, "months"), last))

chartSeries(to.monthly(WMT), 
            major.ticks='months',
            subset='last 10 years')
addBBands()



Thursday, December 10, 2015

Random Walk in R

M = 150
N = 360

m = matrix(0,nrow=M,ncol=N)
m1 = apply(m, c(1,2), function(x) rnorm(1)) #runif, rnorm
m2 = apply(m1, 1, cumsum)
m2 = t(m2)

hist(m2[,N], 30)

a = mean(m2[,N])
s = sd(m2[,N])^2

sd2 = apply(m2, 1, sd)
matplot(t(m2), type="l")