redis

redis是一个内存数据库。
持久化:
redis需要经常将内存中的数据同步到磁盘来保持持久化。redis支持两种持久化方式:一种是快照(默认);一种是Append-only file(aof)方式。
快照是默认的持久化方式。这种方式是就是将内存中数据以快照的方式写入到二进制文件中,默认的文件名为dump.rdb。可以通过配置设置自动做快照持久 化的方式。我们可以配置redis在n秒内如果超过m个key被修改就自动做快照,下面是默认的快照保存配置
save 900 1 #900秒内如果超过1个key被修改,则发起快照保存
save 300 10 #300秒内容如超过10个key被修改,则发起快照保存
save 60 10000
快照保存过程
1.redis调用fork,现在有了子进程和父进程。
2. 父进程继续处理client请求,子进程负责将内存内容写入到临时文件。由于os的写时复制机制(copy on write)父子进程会共享相同的物理页面,当父进程处理写请求时os会为父进程要修改的页面创建副本,而不是写共享的页面。所以子进程的地址空间内的数 据是fork时刻整个数据库的一个快照。
3.当子进程将快照写入临时文件完毕后,用临时文件替换原来的快照文件,然后子进程退出。
aof具体过程:
1. redis调用fork ,现在有父子两个进程
2. 子进程根据内存中的数据库快照,往临时文件中写入重建数据库状态的命令
3.父进程继续处理client请求,除了把写命令写入到原来的aof文件中。同时把收到的写命令缓存起来。这样就能保证如果子进程重写失败的话并不会出问题。
4.当子进程把快照内容写入已命令方式写到临时文件中后,子进程发信号通知父进程。然后父进程把缓存的写命令也写入到临时文件。
5.现在父进程可以使用临时文件替换老的aof文件,并重命名,后面收到的写命令也开始往新的aof文件中追加。
 
另外redis内存存储结构见http://www.cnblogs.com/xuxm2007/archive/2011/11/28/2266627.html

pthread_attr_t属性

  • 线程属性
 int pthread_attr_init(pthread_attr_t *attr);
 int pthread_attr_destroy(pthread_attr_t *attr);

如果要去除对pthread_attr_t结构的初始化,可以调用pthread_attr_destroy函数。

int pthread_attr_getstack(const pthread_attr_t *restrict attr,void **restrict stackaddr, size_t *restrict stacksize);
int pthread_attr_setstack(pthread_attr_t *attr, void *stackaddr, size_t *stacksize);

这两个函数可以用于管理stackaddr线程属性,也可以管理stacksize线程属性。
对进程来说,虚拟地址空间的大小是固定的,进程中只有一个栈,所以它的大小通常不是问题。但对于线程来说,同样大小的虚拟地址空间必须被所有的线程共享。如果应用程序使用了太多的线程,致使线程栈的累计大小超过了可用的虚拟地址空间,这时就需要减少线程默认的栈大小。另一方面,如果线程调用的函数分配了大量的自动变量或者调用的函数涉及很深的栈帧,那么这时需要的栈大小可能要比默认的要大。
如果希望改变栈的默认大小,又不想自己分配地址,这时用pthread_attr_setstacksize函数就非常有用。

int pthread_attr_getguardsize(const pthread_attr_t *restrict attr, size_t *restrict guardsize);
int pthread_init_setguardsize(pthread_attr_t *attr, size_t guardsize);

线程属性guardsize控制着线程栈末尾之后用以避免栈溢出的扩展内存的大小。这个属性默认设置为PAGESIZE个字节。可以把guardsize线程属性设为0,从而不允许属性的这种特征行为发生:在这种情况下不会提供警戒缓冲区。同样地,如果对线程属性stackaddr作了修改,系统就会假设我们会自己管理栈,并使警戒栈无效,等同于把其设为0.

  • 线程的分离状态
 int pthread_attr_getdetachstate(const pthread_attr_t *restrict attr, int *deachstate);
 int pthread_attr_setdetachstate(pthread_attr_t *attr, int detachstate);

如果在创建线程时就知道不需要了解线程的终止状态,则可以修改pthread_attr_t结构中的detachstate线程属性,让线程以分离状态启动。可以使用pthread_attr_setdetachstate把线程属性detachstate设置为下面两个合法值之一:PTHREAD_CREATE_DETACHED,以分离状态启动线程;PTHREAD_CREATE_JOINABLE,正常启动线程。默认创建的线程是非分离状态的,这种情形下,原有的线程等待创建的线程结束。只有在pthread_join()函数返回时,创建的线程才算终止,才能释放自己占用的系统资源。分离线程没有被其他的线程所等待,当自己运行结束时,线程也就终止了,马上释放系统资源。

  • 线程的调度
int pthread_attr_setschedpolicy(pthread_attr_t *attr,int policy);
int pthread_attr_getschedpolicy(const pthread_attr_t *attr,int *policy);

第1个参数是指向属性对象的指针,第2个参数是调度策略或指向调度策略的指针。调度策略可能的值是先进先出(SCHED_FIFO)、轮转法(SCHED_RR),或其它(SCHED_OTHER)。

  • 线程的继承性
int pthread_attr_getinheritsched(const pthread_attr_t*attr,int *inheritsched);
int pthread_attr_setinheritsched(pthread_attr_t *attr,intinheritsched);

分别用来设置和得到线程的继承性。第一个参数指向属性对象的指针,第二个参数是继承性或者指向继承性的指针。继承性决定调度的参数是从创建的进程中继承还是使用在schedpolicy和schedparam属性中显式设置的调度信息。 继承性的可能值是PTHREAD_INHERIT_SCHED(表示新现成将继承创建线程的调度策略和参数)和PTHREAD_EXPLICIT_SCHED(表示使用在schedpolicy和schedparam属性中显式设置的调度策略和参数)。
如果你需要显式的设置一个线程的调度策略或参数,那么你必须在设置之前将inheritsched属性设置为PTHREAD_EXPLICIT_SCHED.

  • 线程的调度参数
int pthread_attr_getschedparam(const pthread_attr_t *attr,struct sched_param *param);
int pthread_attr_setschedparam(pthread_attr_t *attr,conststruct sched_param *param);

分别用来得到和设置线程的调度参数。sched_param结构体的一个子成员sched_priority控制一个优先权值,大的有限权值对应高的优先权。系统支持的最大和最小的优先权值可以分别通过sched_get_priority_max( int policy )和sched_get_priority_min( int policy )两个函数获得。

  • 设置进程的竞争范围属性
int pthread_attr_setscope(pthread_attr_t *attr,int scope);
int pthread_attr_getscope(pthread_attr_t *attr,int *scope);

竞争返回属性定义一个线程对资源,如CPU,争夺的线程范围。第二个参数为PTHREAD_SCOPE_SYSTEM时,表示与系统中相同调度分配域下所有进程的其他线程进行竞争; 第二个参数为PTHREAD_SCOPE_PROCESS时,表示与同一个进程中同样是以PTHREAD_SCOPE_PROCESS属性创建的其他线程进行竞争。
注:更多关于线程互斥量、读写锁、条件变量的属性设置不在此文中详述,需要查阅时参考《Unix环境高级编程第2版》p318。
线程安全:如果一个函数在同一时刻可以被多个线程安全地调用,就称该函数是线程安全的。
如果一个函数是线程安全的,但这并不能说明对信号处理函数也是可重入的。如果函数对异步信号处理程序的重入是安全的,那么就说函数是异步-信号安全的。

int ftrylockfile(FILE *fp);
void flockfile(FILE *fp); 
void funlockfile(FILE *fp);

可以使用flockfile和ftrylockfile获取与给定FILE对象关联的锁。这个锁是递归的,当占有这把锁的时候,还可以再次获取改锁,这并不会导致死锁。

 pthread_key_create(pthread_key_t *keyp, void (*destructor)(void *));

在分配线程私有数据之前,需要创建与该数据关联的键。这个键将用于获取对线程私有数据的访问权。
创建的键存放在keyp指向的内存单元,这个键可以被进程中的所有线程使用,但每个线程把这个键与不同的线程私有数据地址相关联。创建新键时,每个线程的数据地址设为null值。
除了创建键以外,pthread_key_create可以选择为该键关联析构函数,当线程退出时,如果数据地址已经被置为非null值,那么析构函数会被调用。当线程调用pthread_exit或者线程执行返回,正常退出时,会被调用;但线程如果调用了exit,_exit,_Exit,abort等非正常退出时,就不会调用析构函数。
线程通常使用malloc为线程私有数据分配空间,析构函数通常释放已分配的内存,如果线程没有释放内存就退出了,那么线程所属进程出现了内存泄漏。

 int pthread_key_delete(pthread_key_t *key);

对所有的线程,都可以通过调用pthread_key_delete来取消键与线程私有数据值之间的关联关系。

 void *pthread_getspecific(pthread_key_t key);
 int pthread_setspecific(pthread_key_t, key, const void *value);

键一旦创建,就可以通过调用pthread_setspecific把键和线程私有数据关联起来。可以通过pthread_getspecific函数获得线程私有数据的地址。如果没有线程私有数据值与键关联,pthread_getspecific将返回一个空指针,可以据此确定是否需要调用pthread_setspecific。

 int pthread_sigmask(int how, const sigset_t *restrict set,sigset_t *restrict oset);

pthread_sigmask函数与sigprocmask函数基本相同,除了pthread_sigmask工作在线程中,并且失败时返回错误码,而不像sigprocmask中那样设置errno并返回-1。

 int sigwait(const sigset_t *restrict set, int *restrict signop);

线程可以通过调用sigwait等待一个或多个信号发生。

 int pthread_kill(pthread_t thread, int signo);

要把信号发送到进程,可以调用kill;要把信号发送给线程可以调用pthread_kill。可以传一个0值的signo来检查线程是否存在。如果信号的默认处理动作是终止该进程,那么把信号传递给某个线程仍然会杀掉整个进程。

 int pthrad_atfork(void (*prepare)(void), void (*parent)(void), void (*child)(void));

子进程通过继承整个地址空间的副本,也从父进程那里继承了所有互斥量、读写锁、和条件变量的状态栏。如果父进程包含多个线程,子进程在fork返回以后,如果紧接着不是马上exec的话就需要清理锁状态。
用pthread_atfork函数最多可以安装三个帮助清理锁的函数。prepare fork处理程序由父进程在fork创建子进程之前调用,这个fork处理程序的任务是获取父进程定义的所有锁。parent fork处理程序是在fork创建了子进程以后,但在fork返回之前在父进程环境中调用的,这个fork处理程序的任务是对parent fork处理程序获得的所有锁进行解锁。child fork处理程序在fork返回之前在子进程环境中调用,与parent fork一样,child fork处理程序也必须释放prepare fork处理程序获得的所有锁。

Merge Two Sorted Lists

ListNode* MergeSort(ListNode *left, ListNode*right){
        ListNode* newNode = new ListNode(0);                             //
        ListNode* p = newNode;
        while(left != NULL && right != NULL){
            if(left->val <= right->val){
                p->next = left;
                p = p->next;
                left = left->next;
            }else{
                p->next = right;
                p = p->next;
                right = right->next;
            }
        }
        if(left != NULL)
            p->next = left;
        if(right != NULL)
            p->next = right;
        return newNode->next;
    }

延伸:
在两个有序链表中查找第K大元素。 思路:和有序链表合并思路一样,不过在合并过程中需添加计数,同时需要注意相同大小元素只记1次。

Intel intrinsics函数-SSE、AVX、MMX等指令集简单介绍

MMX指令集支持多种整数类型的运算。MMX定义了64位紧缩整数类型,,对应Intrinsic中的__m64类型,它能一次能处理2个32位整数。

  • —64-bit的MMX寄存器(8个,复用了浮点寄存器的尾部,与x87共用寄存器,缺少浮点指令)
  • —支持在打包的字,字节,双字整数上的SIMD操作
  • —MMX指令用于多媒体和通讯软件

SSE是MMX的超集。SSE指令集只支持单精度浮点运算,直到SSE2指令集才支持双精度浮点数运算。SSE2定义了128位紧缩整数类型,对应Intrinsic中的__m128i类型,它能一次能处理4个32位整数。

  • —包括了70条指令,其中50条SIMD浮点运算指令、12条MMX 整数运算增强指令、8条内存连续数据块传输指令
  • —新增8个XMM寄存器(XMM0-XMM7)
  • —在X86_64中额外增加8个(XMM8-XMM15)
SSE2指令集:

  • —使用了144个新增指令
  • —从64位扩展到了128 位
  • —提供双精度操作支持

—SSE3指令集:

  • —增加13条指令(允许寄存器内部之间运算,浮点数到整数的转换)
  • —超线程性能增强指令可以提升处理器的超线程处理能力

—SSSE3指令集:

  • —扩充了SSE3,增加16条指令
  • —绝对值、相反数等

—SSE4指令集:

  • —新增47条指令,更新至SSE4.2

AVX指令集只支持单精度和双精度浮点运算。2013年Haswell架构中的AVX2指令集才支持整数运算。

  • —数据宽度从128位扩展为256位
  • —操作数从两个增加到三个

 

Compiler Auto Vectorization

-x flag, which tells the compiler to generate specific vectorization instructions.
Using the -xHost flag enables the highest level of vectorization supported on the processor on which the user compiles. Note that the Intel compiler will try to vectorize a code with SSE2 instructions at optimizations of -O2 or higher. Disable this by specifying -no-vec.
The Intel compiler can generate a single executable with multiple levels of vectorization with the -ax flag, which takes the same options as the -x flag (i.e., AVX, …, SSE2). This flag will generate run-time checks to determine the level of vectorization support on the processor and will then choose the optimal execution path for that processor. It will also generate a baseline execution path that is taken if the -ax level of vectorization specified is not supported.
-vec-report flag, which generates diagnostic information regarding vectorization to stdout. The -vec-report flag takes an optional parameter that can be a number between 0 and 5 (e.g., -vec-report0), with 0 disabling diagnostics and 5 providing the most detailed diagnostics about what loops were optimized, what loops were not optimized, and why those loops were not optimized.
Intel intrinsics guide:
https://software.intel.com/sites/landingpage/IntrinsicsGuide/

求数组的字数组之和的最大值

思路:给定一个数组A, 找其中和最大的子串,可以可以从A[0]开始,往后累加和放在start中,如果start<0,将可以抛弃当前元素值,不再进行累加,maxSum保存最大的子串和。。并从下一个位置重复上述过程。

/*******************************************
   Author        : Jun Zhang
   Email         : ewalker.zj@gmail.com
   Last Modified : 2015-08-02 14:08
   Filename      : subMax.cpp
   Description   :
*******************************************/
#include<iostream>
int subMax(int *data, int n)
{
   	int start = data[0];           // record the current sum, >0
   	int maxSum = data[0];          // the maxSum
   	for(int i = 1; i < n; i++)
   	{
      		if(start < 0)             // preSum < 0
         			start = 0;            // new start position
      		start += data[i];
      		if(start > maxSum)
         			maxSum = start;
   	}
   	return maxSum;
}
int main()
{
   	int buf[10] = {2, -4, 5, 6, 2, -3, 8, 1, -12, -3};
   	std::cout<<subMax(buf, 10)<<std::endl;
   	return 0;
}

时间复杂度O(n),空间复杂度O(1)
3种变形:
1、求字数组和的绝对值的最大值
2、返回最大字数组位置
 

//需返回最大字数组的位置
struct outInfo
{
   	int begin;
   	int end;
   	int sum;
   	struct outInfo *next;
};
int subMax1(int *data, int n)
{
   	int start data[0];
   	int maxSum = data[0];
   	int pos;
   	int begin = 0, end;
   	int new;
   	outInfo *p, *info, *head;
   	head = (outInfo*)malloc(sizeof(outInfo));
   	p = head;
   	int ret = 0;
   for(int i = 1; i < n; i++)
   	{
     		if(start < 0)
     		{
       			if(ret == 0){
       				start = 0;
				       //此处可以保存当前字数组信息
       				ret = -1;
       				if(maxSum > p->sum)          // 子数组和大于当前存储值,覆盖
       				{
					          p->begin = begin;
          					p->end = end;
          					p->sum = maxSum;
       				}
       				else if(maxSum == p->sum)    // 相同的子数组和
       				{
          					info = (outInfo*)malloc(sizeof(outInfo));
          					info->begin = begin;
          					info->end = end;
          					info->sum = maxSum;
          					info->next = NULL;
          					p->next = info;
          					p = p->next;
       				}
     			}
   		}
  		if((ret == -1))&&(data[i] > 0))
  		{
			     begin = i;                // new begin;
			     ret = 0;
  		}
		  start += data[i];
  		if(start > maxSum)
  		{
     			maxSum = start;
     			end = i;
  		}
	}
  	if(ret == 0)
  	{
     		if(maxSum > p->sum)
     		{
        			p->begin = begin;
        			p->end = end;
        			p->sum = maxSum;
     		}
		     else if(maxSum == p->sum)
     		{
        			info =(outInfo*)malloc(sizeof(outInfo));
        			info->begin = begin;
        			info->end = end;
        			info->sum = maxSum;
        			info->next = NULL;
        			p = p->next;
     		}
   	}
	return maxSum;
}

 
3、数组收尾相连