Inside The C++ Object Model 学习笔记(I)

最近一直在看 Inside The C++ Object Model, 希望从这本书中了解一下底层对象模型的设计,也为以后研究JVM的对象模型做铺垫。

注:由于这本书比较老,最新也就是C++ 98标准。因此这些总结都是基于C++ 98标准的。如果有C++ 11中新增的特性或新的优化(貌似析构函数那一部分变了挺多),我会单独指出。

这篇将总结C++的构造函数语义学相关的内容( Inside The C++ Object Model, Chapter 2 )。第二章主要讲述了构造函数的相关模型及事项。

Implicit Default Constructor(C++ 98)

在我们没有声明默认构造函数的时候,编译器有可能会为我们自动生成默认构造函数。不过,并非在所有情况下,编译器都自动生成default constructor。当且仅当以下四种情况下,编译器会自动为一个类生成default constructor:

  1. 此类有一个显式地实现了默认构造函数(explicit default constructor)的对象成员变量
  2. 此类的父类显式地实现了默认构造函数
  3. 此类中存在虚函数
  4. 此类间接继承了虚基类

注: C++ 11标准增加了移动构造函数(move constructor),有关移动构造函数相关的东西可以看C++ 11标准。

Copy Constructor(C++ 98)

No Bitwise copy

编译器不能简单地拷贝对象,因为编译器需要保证vptrvtbl的正确性。复制的时候要注意正确赋值。比如:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class A { // virtual base class
public:
explicit A() {}
explicit A(int i):i(i) {}
virtual ~A() {} // virtual deconstructor
virtual int test() {
return this->i;
}
protected:
int i;
};
class B : public virtual A {
};
class C : public virtual A {
};
class D : public b, public C {
};

如果在赋值的时候将sub object赋值给base object,编译器为了确保vptrvtbl的一致性,会对其截断:

1
A a = D{};

Return Value Initialization (Traditional C++)

注:C++ 11以后引入了Copy Elision可以省掉copy的过程。

1
2
3
4
5
6
7
Test genTest() {
Test test;
// do something to wrap the object ...
return test;
}

经过编译器解析后被转化为:

1
2
3
4
5
6
7
8
9
10
11
12
void genTest(Test& __temp) {
Test test;
// <init>
test.Test::Test();
// do something to wrap the object ...
// copy constructor invocation
__temp.Test::Test(test);
return;
}

现在如果执行Test t = genTest()这条语句的话,它会被编译器转化为:

1
2
Test t;
genTest(t);

RVO (Copy Elision)

C++ 11将Copy Elision优化加入C++标准中:

in a return statement in a function with a class return type, when the expression is the name of a non-volatile automatic object (other than a function or catch-clause parameter) with the same cv-unqualified type as the function return type, the copy/move operation can be omitted by constructing the automatic object directly into the function’s return value

调用消耗:copy > move > RVO

浅拷贝和深拷贝

老生常谈的东西了,对于指针变量(或数组),必须执行按地址拷贝,这是默认生成的拷贝构造函数不能提供的。因此如果成员变量里有指针型或数组型变量,那么必须自己实现拷贝构造函数,用 memcpymemcopy 进行按地址拷贝。

Move Constructor(C++ 11)

待总结…


参考资料

消息队列中间件 | RabbitMQ 总结

最近学习架构设计的时候经常看见基于消息的架构。这里就来总结一下一个常见的高性能消息队列中间件——RabbitMQ,它支持各种各样的消息队列协议(如JMS和AMQP),并且消息传递比较可靠,并发效率也比较高(RabbitMQ的实现语言是大名鼎鼎的Erlang,天生支持高并发)。这里就来总结一下RabbitMQ的基本使用,以及消息队列和消息架构的一些注意事项。

生产者-消费者模型

Intro

最简单的消息队列模型应该就是 生产者-消费者模型 了。简单的一对一模型如下图:

其中P代表生产者(Producer),C代表消费者(Consumer),中间部分代表消息队列(Message Queue)。

下面我们用RabbitMQ来实现,首先是生产者一端:

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
import com.rabbitmq.client.Channel;
import com.rabbitmq.client.Connection;
import com.rabbitmq.client.ConnectionFactory;
public class Producer {
private static final String QUEUE_NAME = "test_q1";
public static void main(String[] args) throws Exception {
//步骤一:建立连接
ConnectionFactory factory = new ConnectionFactory();
factory.setHost("localhost");
//factory.setPort(6666);
Connection connection = factory.newConnection();
Channel channel = connection.createChannel();
//步骤二:定义消息队列
channel.queueDeclare(QUEUE_NAME, false, false, false, null);
String message = "[Message Producer] 66666";
//步骤三:发布消息
channel.basicPublish("", QUEUE_NAME, null, message.getBytes("UTF-8"));
System.out.println("[MessageQueue] Message sent => message=" + message);
//关闭连接
channel.close();
connection.close();
}
}

消费者一端:

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
import com.rabbitmq.client.*;
import java.io.IOException;
public class Recv {
private static final String QUEUE_NAME = "test_q1";
public static void main(String[] args) throws Exception {
//步骤一:建立连接
ConnectionFactory factory = new ConnectionFactory();
factory.setHost("localhost");
Connection connection = factory.newConnection();
Channel channel = connection.createChannel();
//步骤二:创建一个消费者对象,并利用handleDelivery回调函数接受消息
Consumer consumer = new DefaultConsumer(channel) {
@Override
public void handleDelivery(String consumerTag, Envelope envelope, AMQP.BasicProperties properties, byte[] body) throws IOException {
String msg = new String(body, "UTF-8");
System.out.println("[Message Recv] => " + msg);
}
};
//步骤三:将消费者端与消息队列绑定
channel.basicConsume(QUEUE_NAME, false, consumer);
}
}

可以看到,无论是消费者端还是生产者端,首先要建立通信连接(ConnectionFactory -> Connection -> Channel)。

这只是最简单的一种情况,后边将介绍更普遍、更复杂的情况。

定义消息队列

定义消息队列可以用Channel接口的queueDeclare方法,它有两个重载版本。含参的queueDeclare方法定义如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
* Declare a queue
* @see com.rabbitmq.client.AMQP.Queue.Declare
* @see com.rabbitmq.client.AMQP.Queue.DeclareOk
* @param queue the name of the queue
* @param durable true if we are declaring a durable queue (the queue will survive a server restart)
* @param exclusive true if we are declaring an exclusive queue (restricted to this connection)
* @param autoDelete true if we are declaring an autodelete queue (server will delete it when no longer in use)
* @param arguments other properties (construction arguments) for the queue
* @return a declaration-confirm method to indicate the queue was successfully declared
* @throws java.io.IOException if an error is encountered
*/
Queue.DeclareOk queueDeclare(String queue, boolean durable, boolean exclusive, boolean autoDelete,
Map<String, Object> arguments) throws IOException;

可以看到,它接受五个参数。第一个参数对应消息队列名称,第二个参数对应消息队列是否可以持久化,第三个参数对应消息队列是否仅限于当前连接,第四个参数对应消息队列是否在不用的情况下自动删除,第五个参数对应消息队列其他的一些设置。

另外还有一个无参的queueDeclare方法,实现如下:

1
2
3
4
public com.rabbitmq.client.AMQP.Queue.DeclareOk queueDeclare()
throws IOException {
return queueDeclare("", false, true, true, null); // 默认不可持久化
}

注意:Producer端和Consumer端的消息队列定义需要保持一致。

Envelope对象

Envelope对象封装了AMQP通信需要的数据,如deliveryTag, redeliver flag, exchange, routingKey等。其构造函数注释中有这几个变量的解释:

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
* Construct an {@link Envelope} with the specified construction parameters
* @param deliveryTag the delivery tag
* @param redeliver true if this is a redelivery following a failed ack
* @param exchange the exchange used for the current operation
* @param routingKey the associated routing key
*/
public Envelope(long deliveryTag, boolean redeliver, String exchange, String routingKey) {
this._deliveryTag = deliveryTag;
this._redeliver = redeliver;
this._exchange = exchange;
this._routingKey = routingKey;
}

消息分发机制(Dispatch)

RabbitMQ采用 轮询分发机制(Round-robin dispatching),每个消费者将接收到数量相近的消息。

扩展:如果想控制每次给消费者端传递的消息数量(流量控制),可以通过ChannelbasicQos方法,它有三个重载版本:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
* Request specific "quality of service" settings.
*
* These settings impose limits on the amount of data the server
* will deliver to consumers before requiring acknowledgements.
* Thus they provide a means of consumer-initiated flow control.
*/
public void basicQos(int prefetchSize, int prefetchCount, boolean global)
throws IOException {
exnWrappingRpc(new Basic.Qos(prefetchSize, prefetchCount, global));
}
/** Public API - {@inheritDoc} */
public void basicQos(int prefetchCount, boolean global)
throws IOException {
basicQos(0, prefetchCount, global);
}
/** Public API - {@inheritDoc} */
public void basicQos(int prefetchCount)
throws IOException {
basicQos(0, prefetchCount, false);
}

其中:

  • prefetchSize表示服务器给消费者端传递数据大小的上限,0为不限
  • prefetchCount表示服务器给消费者端传递数据数量的上限,0为不限
  • global标志位表示此设置是否应用于整个Channel而不是每个Consumer

消息确认机制(Acknowledge)

设想一下这种场景:消费者端处理一个耗时任务时被强制结束任务,此时任务还没有完成,但是消息却已从消息队列中发送了出去。如果没有一定的消息确认机制,那么我们将丢失掉此消息及后面一堆发送至此消费者但还未经处理的消息。

RabbitMQ支持消息确认机制。如果消费者已处理完任务,那么它将向Broker发送ACK消息,告知某条消息已被成功处理,可以从队列中移除。如果消费者端没有发送回ACK消息,那么Broker会认为消息处理失败,会将此消息及后续消息分发给其他消费者端进行处理(redeliver flag置为true)。

这种确认机制和TCP/IP协议确立连接类似。不同的是,TCP/IP确立连接需要经过三次握手,而RabbitMQ只需要一次ACK。

注意:RabbitMQ当且仅当检测到ACK消息未发出且消费者端的连接终止时才会将消息重新分发给其他消费者端,因此不需要担心消息处理时间过长而被重新分发的情况。

我们可以通过设置basicConsume方法的autoAck标志位来设置其消息确认机制。basicConsume方法的定义如下:

1
String basicConsume(String queue, boolean autoAck, Consumer callback) throws IOException;

autoAck为true时,不启用显式消息确认机制,消息分发出去即为确认完毕。autoAck为false时,启用上述的消息确认机制。

消费者端发送ACK消息可以通过在回调函数中调用Channel的basicAck方法实现:

1
channel.basicAck(envelope.getDeliveryTag(), false);

其定义如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
* Acknowledge one or several received
* messages. Supply the deliveryTag from the {@link com.rabbitmq.client.AMQP.Basic.GetOk}
* or {@link com.rabbitmq.client.AMQP.Basic.Deliver} method
* containing the received message being acknowledged.
* @see com.rabbitmq.client.AMQP.Basic.Ack
* @param deliveryTag the tag from the received {@link com.rabbitmq.client.AMQP.Basic.GetOk} or {@link com.rabbitmq.client.AMQP.Basic.Deliver}
* @param multiple true to acknowledge all messages up to and
* including the supplied delivery tag; false to acknowledge just
* the supplied delivery tag.
* @throws java.io.IOException if an error is encountered
*/
void basicAck(long deliveryTag, boolean multiple) throws IOException;

WARNING:使用的时候千万不要忘了调用basicAck方法!必要的时候可以对Consumer类再做一层封装。

简单的消息持久化(Message durability)

RabbitMQ的消息确认机制保证了即使消费者端挂了,我们的消息也可以被顺利处理。然而,如果碰上意外情况,Broker(RabbitMQ Server)挂了(比如意外重启),这种情况下不做任何设置的话,我们的信息仍然会丢失。好在,RabbitMQ同样提供了消息持久化的功能。

首先,我们需要保证我们的消息队列可以持久化,方法上面已经提到过,就是将queueDeclare方法的durable标志位设为true。

然后,我们需要在发布消息的时候通过设置basicPublish方法的props参数为PERSISTENT_TEXT_PLAIN来实现消息可持久化,比如:

1
2
channel.basicPublish("", TASK_QUEUE_NAME, MessageProperties.PERSISTENT_TEXT_PLAIN,
message.getBytes("UTF-8"));

注意:尽管设置了消息可持久化,但这并不能完全保证消息就一定可以存储到磁盘里。RabbitMQ存在一段时间,接受了一个消息但还没来得及存储。并且,RabbitMQ不一定对所有消息都做fsync(即同步内存中的消息到硬盘),有些消息可能只是被缓存而不会被持久化。因此,这种消息持久化机制是不可靠的,特别是对大型项目。如果需要可靠的消息持久化,可以使用 publisher confirm

Exchange

在RabbitMQ中,producer并不是直接将消息发送到message queue中,而是将它传递给一种叫exchage的结构。顾名思义,exchange用于交换消息,它接受publisher发送的消息,并按照一定的策略传递给下层的消息队列,最后传递到对应的subscriber中。Exchange有好几种:direct, topic, headers, fanout等,分别对应不同的消息分发策略。

在消费者一端,我们需要通过queueBind函数将消息队列绑定到对应的exchange上;如果没有绑定,则RabbitMQ会给其指定一个匿名exchage(即上面生产者-消费者模型中的exchange)。

发布/订阅模型

发布-订阅模型也是一种典型的消息模型,它相当于一个“一对多”模型,也就是说publisher可以向多个subscriber发送消息。我们可以用下面的图来表示这种模型:

在RabbitMQ中,我们可以通过exchange来实现发布-订阅模型。我们需要在订阅者一端将期望接收消息的队列绑定到我们定义的exchange上(最简单的fanout广播类型即可),然后在发布者端将消息发布至定义的exchange上即可。

路由与模式匹配

RabbitMQ还支持路由模式,即像路由那样根据path来分派消息,只要在queueBind函数中指定感兴趣的routingKey即可。路由模式下我们一般使用direct类型的exchange,它会将与队列binding key匹配的消息分发到指定的队列中。

当然如果我们需要根据path的模式来匹配的话,我们可以使用topic类型的exchange,它可以用于匹配多种pattern下的path并且分发消息。

RPC

消息队列可以用来实现RPC。我们可以利用消息队列的API封装一个RPC代理类,调用端在通过RPC Proxy调用方法时,调用端会将调用方法的元数据(名称,参数等)包装成一条消息,然后通过相应的消息队列发送至集群的另一节点中,被调用者接收到此消息,将其解码后在本地进行方法调用(LPC)。如果需要返回结果,那么被调用端在方法调用完毕后将结果包装成消息,通过消息队列再发送回调用端即可。这就是用消息队列实现RPC的一般思路。

在RabbitMQ中,实现RPC的思路比较简单:使用两个队列,分别处理调用请求及调用回复即可:

注意RPC的调用时间可能会比较长(受到网络、本地调用执行时间等因素影响),因此可能会阻塞执行线程,这也是RPC为人诟病的一点。我们可以对其稍加改造,改成异步模式,这样会使整个系统更加灵活。

与其他消息队列的对比

TODO: 待分析;后面有时间研究研究ZeroMQ和Kafka的设计及实现。


参考资料

不动点组合子 | Y Combinator

在现代编程语言中,函数都是具名的,而在传统的Lambda Calculus中,函数都是没有名字的。这样就出现了一个问题 —— 如何在Lambda Calculus中实现递归函数,即匿名递归函数。Haskell B. Curry发现了一种不动点组合子 —— Y Combinator,用于解决匿名递归函数实现的问题。

Fixed-point combinator

我们先来看看不动点组合子的定义。不动点组合子(fixed-point combinator)是一个满足以下等式的高阶函数$y$:

$$\forall f, \ y \ f = f \ (y \ f)$$

如果令 $x = f \ x$,那么这其实就是一个求解函数不动点的问题:

$$x = f \ x$$

Y Combinator

那么不动点组合子有什么用呢?假设我们想要求阶乘,我们通常会用递归来实现:

1
2
3
factorial :: Int -> Int
factorial 0 = 0
factorial n = n * factorial (n - 1)

在上面的例子中,factorial函数体里面引用了自身。用pseudo lambda calculus可以表示为:

$$f = \lambda n. \ if \ (n == 0) \ 0 \ else \ n * f(n - 1)$$

但是Lambda演算中函数是没有名字的,所以这个地方是没法在函数体内调用f的。那怎么处理呢?我们可以通过某种“黑魔法”实现间接递归 —— 把自己算出来。我们不妨假设一个函数self代表一个“Lambda Calculus中真正的”递归函数,则上式可以改写为:

$$f = \lambda n. \ if \ (n == 0) \ 0 \ else \ n * self(n - 1)$$

我们现在把self函数参数化,设此函数为G

$$G = \lambda n \ \lambda g. \ if \ (n == 0) \ 0 \ else \ n * g(n - 1)$$

应用 $\beta-reduction$,我们会发现:

$$G \ f = \lambda n. \ if \ (n == 0) \ 0 \ else \ n * f(n - 1)$$

即 $G \ f = f$。

然而这还不够,这里就需要引入不动点组合子了。假设不动点组合子 $Y = \lambda \ f. f (Y \ f)$,且 $f = Y \ G$,那么 $Y G = G (Y \ G) = G \ f = f$,这就表示出f来了!

所以我们需要找到一个与 $Y$ 等效的闭合Lambda表达式,其中最著名的就是Curry发现的 Y Combinator:

$$Y = \lambda f. (\lambda x . f \ (x \ x)) (\lambda x. f \ (x \ x))$$

通过 $\beta-reduction$ 验证:

$$Y \ g = \lambda f. (\lambda x . f \ (x \ x)) (\lambda x. f \ (x \ x)) \ g$$

$$= (\lambda x. g \ (x \ x)) (\lambda x. g \ (x \ x)$$

$$= g \ ((\lambda x. g \ (x \ x) \ (\lambda x. g \ (x \ x))$$

$$= g \ (Y \ g)$$

一颗赛艇!至于Y Combinator是如何推出来的,可以参考 康托尔、哥德尔、图灵——永恒的金色对角线 这篇文章,写的非常完美。

Haskell实现

我们先尝试直接用函数表示:

1
fix f = (\x -> f (x x)) (\x -> f (x x))

GHC会提示错误:

1
2
3
4
5
6
7
8
9
10
<interactive>:6:25:
Occurs check: cannot construct the infinite type: r0 ~ r0 -> t
Expected type: r0 -> t
Actual type: (r0 -> t) -> t
Relevant bindings include
x :: (r0 -> t) -> t (bound at <interactive>:6:15)
f :: t -> t (bound at <interactive>:6:9)
fix :: (t -> t) -> t (bound at <interactive>:6:5)
In the first argument of ‘x’, namely ‘x’
In the first argument of ‘f’, namely ‘(x x)’

这里的问题在于x的类型是infinite type,无法在Haskell表示出来(Hindley–Milner类型系统的限制)。参考Reddit上的解决方案,我们需要绕个弯,定义一个Mu算子来绕过类型检查:

1
2
3
newtype Mu a = Mu (Mu a -> a)
y f -> (\h -> h $ Mu h) (\x -> f . (\(Mu g) -> g) x $ x)

当然还有个更加贴近Y Combinator原本意思的实现:

1
2
3
4
5
6
7
8
9
10
newtype Mu f = Mu {unMu :: f (Mu f)}
unfold = unMu
fold = Mu
newtype X' b a = {unX :: a -> b}
type X a = Mu (X' a)
unfold' = unX . unfold
fold' = fold . X'
y f = (\x -> f (unfold' x x)) $ fold' (\x -> f (unfold' x x))

References

Haskell 学习笔记 | 范畴论与 Haskell(基础篇)

最近入了 Haskell 的坑了。俗话说得好,一入 FP 深似海,从此 Monad 皆是自函子范畴上的幺半群。。。本篇文章主要总结范畴论基础。。。

Category

一个 范畴 $C$ 由以下三部分组成:

  • 一些 对象(object)构成的类 $ob(C)$
  • 范畴 $C$ 中对象之间的映射,称为 态射(morphism)。对于范畴 $C$ 中任意两个object $A$、$B$,所有的 $A \to B$ 态射的集合用 $hom(A, B)$ 表示,其中 $A$ 称为domain,$B$称为codomain
  • 态射的复合运算($\circ$),用于将多个态射进行复合。比如 $f: \ A \to B$, $g: \ B \to C$,则$g \circ f: \ A \to C$

对范畴中的每一个 object $X$,都存在对应的幺元 $id_{X}: X \to X$ ,并且满足关系:

$$ id(B) \circ f = f = f \circ id(A) $$

同时,复合运算是可结合的,比如 $ (h \circ g) \circ f = h \circ (g \circ f) $。

在 Haskell 中,对应的是:

  • object对应着某个具体的函数(类型?)(这是我的理解,也有很多人认为对象对应着某一类值的集合,即类型。我的理解是type和type constructor都可以看作是function
  • 态射对应着函数之间的映射,这种映射产生新的函数。比如 $f :: (a \to b) \to a \to b$
  • 态射的复合运算代表着函数的复合(复合函数),比如 h = f . g

Functor

在范畴论中,morphism 是 object 与 object 之间的映射。那么肯定还有 category 与 category 之间的映射,这称为函子(Functor)。

既然是范畴之间的映射,那么函子F的作用就有两个:

  • 将范畴C的object($X$)映射到范畴D的object ($F(X)$)
  • 将范畴C的morphism($f: \ X \to Y$)映射到范畴D的morphism($F(f) : \ F(x) \to F(Y)$)

并且需要满足两个条件:

  • 单位态射关系:$\forall X \in C, F(id_{X}) = id_{F(X)}$
  • 分配率:$\forall f:X \to Y, g: Y \to Z \in C, F(g \circ f) = F(g) \circ F(f)$

一般的函子都是协变函子(covariant functor)。将函子中的某个范畴 $C$ 替换为其对偶范畴 $C^{OP}$ 即可得到逆变函子(contravariant functor): $F \ : \ C^{OP} \to D$。

将范畴映射到自身的函子称为自函子(endofunctor),即把范畴C的对象和态射映射到自身。自函子反映了范畴内部的自相似性。

Functor

在Haskell中,Functor是一个 typeclass,它是这样定义的:

1
2
class Functor f where
fmap :: (a -> b) -> f a -> f b

其中f是一个 type constructor,它接收一个concrete type(实际类型)以构造出一个concrete type,其kind为* -> *

如果这里的object对应Haskell里的类型的话,那么type constructor相当于morphism,它就是自函子的一部分,即一个范畴的object与另一个范畴的object的映射。

类型与类型的映射一般都是简单类型与复杂类型之间的相互转化,比如int -> Maybe int。而另一部分,即态射与态射之间的映射,其实就是高阶函数(函数与函数之间的映射,因为态射本身就对应Haskell中的函数),在Haskell的Functor里面对应的就是fmap,它将态射a -> b映射为另一个态射f a -> f b:

$$(a \to b) \to f \ a \to f \ b$$

Bifunctor

Bifunctor(二元函子)与普通的Functor区别之处在于Bifunctor的domain为两个范畴的积,比如 $F: \ C_{1} \times C_{2} \to D$。

Hom-functor

对于一个范畴 $C$,其 hom-functor 的定义为:$Hom(-,-) : \ C^{OP} \times C \to Set$,它是一个bifunctor。

从hom-functor中衍生出的两个函子:

  • covariant hom-functor: $Hom(A, -): \ C \to Set$,通常称为 copresheaf
  • contravariant hom-functor: $Hom(-, A): \ C^{OP} \to Set$,通常称为 presheaf

Representable functor

若函子 $F: \ C \to Set$ 自然同构于 $Hom(A, -)$,其中 $A \in C$,则 $F$ 就是一个Representable functor。

相似地,若函子 $F: \ C^{OP} \to Set$ 自然同构于 $Hom(-, A)$,其中 $A \in C$,则 $F$ 就是一个Corepresentable functor。

注:Forgetful functors to $Set$ are very often representable.

Adjoint functor

若有两个函子 $F: \ D \to C$ 以及 $G : \ C \to D$ 满足以下自然同构关系:

$$Hom_{C}(F(-), -) \cong Hom_{D}(-, G(-))$$

即对于 $\forall X \in C, Y \in D$,满足:

$$Hom_{C}(F(Y), X) \cong Hom_{D}(Y, G(X))$$

那么这两个函子就是一对伴随函子(adjoint functor),并称F是G的左伴随函子,记为 $F \dashv G$。

  • 常见的一对伴随函子:Forgetful Functor/Free Functor。$Forget : \ C \to Set$,$Free : \ Set \to C$,$Free \dashv Forget$。

Natural Transformation

再抽象一层,自然变换(Natural Transformation)是Functor之间的映射关系。

假设 $F$ 和 $G$ 是范畴 $C$ 到范畴 $D$ 的函子 $C \to D$,则 $F$ 到 $G$的自然变换 $\tau : F \to G$ 是一个作用于 $C$ 中任意对象 $X$ 的 D-morphism :$\tau_{X} : F X \to G X$,且满足以下naturality condition(用交换图表示):

Natural Transformation

Monad

这里先总结一下 Monad 的范畴论定义。Monad 由三元组 $<T, \eta, \mu>$ 构成。其中:

  • $T$ 为范畴 $X$ 上的自函子: $T: X \to X$
  • $\eta$ 为单位自函子 $id_{X}$ 到函子 $T$ 的自然变换:$\eta: id_{X} \to T$
  • $\mu$ 为函子 $T$ 的张量积 $T \circ T$ 到函子 $T$ 的自然变换:$\mu: T \circ T \to T$

同时它需要满足以下 coherence condition:

  • $\mu \circ T \mu = \mu \circ \mu T$ (即自然变换 $T^{3} \to T$)
  • $\mu \circ T \eta = \mu \circ \eta T = 1_{T}$ (即自然变换 $T \to T$)

用交换图表示如下:

Monad coherence condition

注1:此处函子的张量积 $\otimes$ 可以看作为组合(composition)。

注2:注意结合 Monoidal Category 理解;注意里面的Monoid与抽象代数中幺半群的区别。

TODO

  • Monoidal Category / Monoidal Functor
  • Monad 的来源、推导
  • Kleisli 范畴下 Monad 的定义
  • Free Monad
  • Yoneda Lemma
  • Yoneda Embedding/Profunctor
  • Day Convolution
  • Kan Extensions
  • Universal Construction

参考资料

Android 事件分发机制总结

事件构成

在Android中,事件主要包括点按、长按、拖拽、滑动等,点按又包括单击和双击,另外还包括单指操作和多指操作。所有这些都构成了Android中的事件响应。总的来说,所有的事件都由如下三个部分作为基础:

  • 按下(ACTION_DOWN)
  • 移动(ACTION_MOVE)
  • 抬起(ACTION_UP)

所有的操作事件首先必须执行的是按下操作(ACTION_DOWN)。

Android事件分发机制

Android事件分发是先传递到ViewGroup,再由ViewGroup传递到View的。

对于View:

大体流程:触摸动作发生 => 调用dispatchTouchEvent方法 => 首先调用onTouch方法

若同时满足:绑定了OnClickListener、控件可用(enabled)、onTouch方法返回true,则dispatchTouchEvent方法将直接返回true,不会调用onTouchEvent方法。

这是最新的代码:

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
public boolean dispatchTouchEvent(MotionEvent event) {
// If the event should be handled by accessibility focus first.
if (event.isTargetAccessibilityFocus()) {
// We don't have focus or no virtual descendant has it, do not handle the event.
if (!isAccessibilityFocusedViewOrHost()) {
return false;
}
// We have focus and got the event, then use normal event dispatch.
event.setTargetAccessibilityFocus(false);
}
boolean result = false;
if (mInputEventConsistencyVerifier != null) {
mInputEventConsistencyVerifier.onTouchEvent(event, 0);
}
final int actionMasked = event.getActionMasked();
if (actionMasked == MotionEvent.ACTION_DOWN) {
// Defensive cleanup for new gesture
stopNestedScroll();
}
if (onFilterTouchEventForSecurity(event)) {
//noinspection SimplifiableIfStatement
ListenerInfo li = mListenerInfo;
if (li != null && li.mOnTouchListener != null
&& (mViewFlags & ENABLED_MASK) == ENABLED
&& li.mOnTouchListener.onTouch(this, event)) {
result = true;
}
if (!result && onTouchEvent(event)) {
result = true;
}
}
if (!result && mInputEventConsistencyVerifier != null) {
mInputEventConsistencyVerifier.onUnhandledEvent(event, 0);
}
// Clean up after nested scrolls if this is the end of a gesture;
// also cancel it if we tried an ACTION_DOWN but we didn't want the rest
// of the gesture.
if (actionMasked == MotionEvent.ACTION_UP ||
actionMasked == MotionEvent.ACTION_CANCEL ||
(actionMasked == MotionEvent.ACTION_DOWN && !result)) {
stopNestedScroll();
}
return result;
}

否则,将会继续调用onTouchEvent方法。并且可以推断,onClick方法也是在onTouchEvent方法中调用的。

对于ViewGroup

  1. Android事件分发是先传递到ViewGroup,再由ViewGroup传递到View的。
  2. 在ViewGroup中可以通过onInterceptTouchEvent方法对事件传递进行拦截,onInterceptTouchEvent方法返回true代表不允许事件继续向子View传递,返回false代表不对事件进行拦截,默认返回false。
  3. 子View中如果将传递的事件消费掉,ViewGroup中将无法接收到任何事件。

总结

  1. Android中事件按照从上到下的顺序进行层级传递,事件处理从Activity开始到ViewGroup再到View
  2. 事件传递方法包括dispatchTouchEventonTouchEventonInterceptTouchEvent,其中前两个是ViewViewGroup都有的,最后一个是只有ViewGroup才有的方法。这三个方法的作用分别是负责事件分发、事件处理、事件拦截
  3. onTouch事件要先于onClick事件执行,onTouch在事件分发方法dispatchTouchEvent中调用,而onClick在事件处理方法onTouchEvent中被调用,onTouchEvent要后于dispatchTouchEvent方法的调用

Android MVP 架构重构实践

我们之前的架构就是普通的MVC架构。由于各种layout文件职责单一,因此Activity经常也作为Controller层,这样可能会堆出一个几千行的Activity,看起来就很爽。。因此,这次总结项目时便计划用更好的MVP架构和MVVM架构来重构项目。

为了简便起见,就拿LoginActivity来练手吧,这还属于逻辑比较简单的。。这是原登录逻辑的大概代码(省略了大量逻辑):

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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
public class LoginActivity extends BaseActivity {
@Bind(R.id.et_username)
EditText etUserName;
@Bind(R.id.et_password)
EditText etPassword;
private String mUserName = "";
private String mPassword = "";
@Override
protected int getLayoutId() {
return R.layout.activity_login;
}
@Override
public boolean onOptionsItemSelected(MenuItem item) {
switch (item.getItemId()) {
case android.R.id.home:
onBackPressed();
break;
default:
break;
}
return super.onOptionsItemSelected(item);
}
@Override
protected boolean hasBackButton() {
return true;
}
@Override
protected int getActionBarTitle() {
return R.string.login;
}
@Override
@OnClick({R.id.btn_login, R.id.iv_qq_login, R.id.iv_wx_login, R.id.iv_sina_login})
public void onClick(View v) {
int id = v.getId();
switch (id) {
case R.id.btn_login:
handleLogin();
break;
case R.id.iv_qq_login:
qqLogin();
break;
case R.id.iv_wx_login:
wxLogin();
break;
case R.id.iv_sina_login:
sinaLogin();
break;
default:
break;
}
}
private boolean okForLogin() {
if (!DeviceUtil.hasInternet()) {
ToastUtil.toast(R.string.tip_no_internet);
return false;
}
....
return true;
}
private final BaseJsonHttpResponseHandler mHandler = new BaseJsonHttpResponseHandler() {
@Override
public void onSuccess(int statusCode, Header[] headers, String rawJsonResponse, Object response) {
if(response != null) {
handleLoginResult((LoginResult)response);
}
}
@Override
public void onFailure(int statusCode, Header[] headers, Throwable throwable, String rawJsonData, Object errorResponse) {
ToastUtil.toast("网络出现错误,请重试。(" + statusCode + ")");
}
@Override
protected Object parseResponse(String rawJsonData, boolean isFailure) throws Throwable {
return JsonUtil.resolveLoginResult(rawJsonData);
}
@Override
public void onFinish() {
super.onFinish();
hideWaitDialog();
}
};
private void handleLogin() {
if(!okForLogin())
return;
mUserName = etUserName.getText().toString();
mPassword = etPassword.getText().toString();
hideKeyboard();
showWaitDialog(R.string.progress_login).show();
SamsaraAPI.login(mUserName, mPassword, mHandler);
}
private void handleLoginResult(LoginResult result) {
if(result.getDataResult().isOK()) {
...
AppContext.getContext().saveUserInfo(result.getUser());
hideWaitDialog();
handleLoginSuccess();
}
else {
AppContext.getContext().cleanLoginInfo();
ToastUtil.showToast("错误:" + result.getDataResult().getErrorMsg());
}
}
private void handleLoginSuccess() {
...
ToastUtil.toast("登录成功");
finish();
}
private void qqLogin() {
...
}
private void wxLogin() {
...
}
private void sinaLogin() {
...
}
}

如果登录逻辑很复杂(比如有很多种三方登录逻辑),那么Activity可能会比较臃肿。这时候就要减轻Activity的职责,把代码重构成MVP架构。这个时候Activity作为View层,而把主要业务逻辑放至Presenter层。Presenter层与View层的交互是通过接口实现的。
重构后的架构
IBaseLoginService接口为普通登录接口,IThirdLoginService接口继承普通登录接口,也扩展作为三方扩展登录接口,登录逻辑的具体实现在LoginServiceImpl类里。
我们把登录接口设计成这样:

1
2
3
4
5
public interface IBaseLoginService {
void login(String username, String password, LoginResultCallback callback);
}

1
2
3
4
5
6
7
8
public interface IThirdLoginService extends IBaseLoginService {
void wxLogin(String username, String password, LoginResultCallback callback);
void qqLogin(String username, String password, LoginResultCallback callback);
void weiboLogin(String username, String password, LoginResultCallback callback);
}

我们同时设计了登录的回调接口,用于处理登录成功或失败的逻辑:

1
2
3
4
5
6
public interface LoginResultCallback {
void onLoginSuccess(LoginResult result);
void onFailure(int error_code);
}

接下来我们在LoginServiceImpl类里实现登录逻辑:

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
public class LoginServiceImpl implements IThirdLoginService {
@Override
public void login(final String username, final String password, final LoginResultCallback callback) {
final BaseJsonHttpResponseHandler mHandler = new BaseJsonHttpResponseHandler() {
@Override
public void onSuccess(int statusCode, Header[] headers, String rawJsonResponse, Object response) {
if(response != null) {
callback.onLoginSuccess((LoginResult)response);
}
}
@Override
public void onFailure(int statusCode, Header[] headers, Throwable throwable, String rawJsonData, Object errorResponse) {
callback.onFailure(statusCode);
}
@Override
protected Object parseResponse(String rawJsonData, boolean isFailure) throws Throwable {
return JsonUtil.resolveLoginResult(rawJsonData);
}
};
new Thread() {
@Override
public void run() {
SamsaraAPI.login(username, password, mHandler);
}
}.start();
}
//TODO:此处省略第三方登录逻辑
@Override
public void wxLogin(String username, String password, LoginResultCallback callback) {
LogUtil.toast("微信API 接口未开放");
}
@Override
public void qqLogin(String username, String password, LoginResultCallback callback) {
LogUtil.toast("QQ API 接口未开放");
}
@Override
public void weiboLogin(String username, String password, LoginResultCallback callback) {
LogUtil.toast("微博API 接口未开放");
}
}

其中,这里对网络的处理用了AsyncHttpClient库,以后也可以替换成Volley;SamsaraAPI是为此App设计的API类。到这里,如果后边三个三方实现比较臃肿的话,整个登录业务逻辑类就显得比较臃肿了,我思考了一下,再把三方逻辑的实现单列一个类,需要的时候继承?不过用继承也不是很好的方法,可以考虑用组合或者装饰模式来实现(此处留待想到更好的设计模式)。

Addition:如果在登录之前需要对登录数据及环境进行处理,且处理逻辑比较多的话,我们可以借助AOP的思想,利用代理模式,将这些通用逻辑(横切面)与特定业务逻辑(纵面)分开,更好地解除耦合。如日志、数据校验之类的逻辑都属于通用逻辑;当然另一种方法就是封装成各种Util类,我这里采用了后一种方法。

MVC与MVP架构(图片来源于网络)

接下来就是View层接口了。前边提到过,Presenter与View是通过接口进行交互的,因此这个View接口如何设计也至关重要。我这里考虑的是,对于我们的一个业务逻辑:

  • 此逻辑需要获取什么数据?
  • 此逻辑进行时需要有什么表现?(比如进度条对话框)
  • 逻辑执行的结果以及对UI的反馈?

比如,对于登录逻辑,我们需要从UI中获取用户名和密码;登录请求发出后需要等待服务器响应,这段时间应该会显示等待对话框;登录响应后,返回登录成功或失败的信息,对应更新UI和数据,因此我设计成:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public interface IBasicLoginView {
String getUsername();
String getPassword();
void handleLoginSuccess();
void showWaiting();
void hideWaiting();
boolean okForLogin();
}

然后就是Presenter的设计了,Presenter与LoginService和LoginView使用组合模式:

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
public class LoginPresenter {
private IThirdLoginService loginService;
private IBasicLoginView loginView;
private Handler mHandler = new Handler();
public LoginPresenter(IBasicLoginView loginView) {
this.loginView = loginView;
this.loginService = new LoginServiceImpl();
}
public void login() {
if(!loginView.okForLogin())
return;
loginView.showWaiting();
loginService.login(loginView.getUsername(), loginView.getPassword(),
new LoginResultCallback() {
@Override
public void onLoginSuccess(final LoginResult result) {
mHandler.post(new Runnable() {
@Override
public void run() {
handleLoginResult(result);
loginView.hideWaiting();
loginView.handleLoginSuccess();
}
});
}
@Override
public void onFailure(int error_code) {
ToastUtil.toast("网络出现错误,请重试。(" + error_code + ")");
}
});
}
private void handleLoginResult(LoginResult result) {
...
}
public void qqLogin() {
loginService.qqLogin("", "", null);
}
public void wxLogin() {
loginService.wxLogin("", "", null);
}
public void sinaLogin() {
loginService.weiboLogin("", "", null);
}
}

最后实现Activity:

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
public class LoginActivity extends BaseActivity implements IBasicLoginView {
@Bind(R.id.et_username)
EditText etUserName;
@Bind(R.id.et_password)
EditText etPassword;
private LoginPresenter presenter = new LoginPresenter(this);
@Override
protected int getLayoutId() {
return R.layout.activity_login;
}
@Override
public boolean onOptionsItemSelected(MenuItem item) {
switch (item.getItemId()) {
case android.R.id.home:
onBackPressed();
break;
default:
break;
}
return super.onOptionsItemSelected(item);
}
@Override
protected boolean hasBackButton() {
return true;
}
@Override
protected int getActionBarTitle() {
return R.string.login;
}
@Override
@OnClick({R.id.btn_login, R.id.iv_qq_login, R.id.iv_wx_login, R.id.iv_sina_login})
public void onClick(View v) {
int id = v.getId();
switch (id) {
case R.id.btn_login:
presenter.login();
break;
case R.id.iv_qq_login:
presenter.qqLogin();
break;
case R.id.iv_wx_login:
presenter.wxLogin();
break;
case R.id.iv_sina_login:
presenter.sinaLogin();
break;
default:
break;
}
}
@Override
public boolean okForLogin() {
if (!DeviceUtil.hasInternet()) {
ToastUtil.toast(R.string.tip_no_internet);
return false;
}
...
return true;
}
@Override
public String getUsername() {
return etUserName.getText().toString();
}
@Override
public String getPassword() {
return etPassword.getText().toString();
}
@Override
public void showWaiting() {
hideKeyboard();
showWaitDialog(R.string.progress_login).show();
}
@Override
public void hideWaiting() {
hideWaitDialog();
}
@Override
public void handleLoginSuccess() {
...
ToastUtil.toast("登录成功");
finish();
}
}

由于这只是练手,原Activity逻辑也不算也别复杂(五百行左右),因此对架构进行重构后并没有看出开发上有什么便捷之处,但以后可能会有更为复杂的逻辑,若不进行适当的重构,Activity可能会超过1000行,特别臃肿,不利于扩展和调BUG。因此,使用MVP/MVVM架构,在一个大项目中是必不可少的。

C++ STL 之哈希表 | unordered_map

C++ STL中,哈希表对应的容器是 unordered_map(since C++ 11)。根据 C++ 11 标准的推荐,用 unordered_map 代替 hash_map

Prologue

先来回顾一下数据结构中哈希表相关的知识。

哈希表是根据关键码值(key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度,这个映射函数叫做散列函数。

哈希表的一个重要问题就是如何解决映射冲突的问题。常用的有两种:开放地址法链地址法

与 map 的区别

STL中,map 对应的数据结构是 红黑树。红黑树是一种近似于平衡的二叉查找树,里面的数据是有序的。在红黑树上做查找操作的时间复杂度为 O(logN)。而 unordered_map 对应 哈希表,哈希表的特点就是查找效率高,时间复杂度为常数级别 O(1), 而额外空间复杂度则要高出许多。所以对于需要高效率查询的情况,使用 unordered_map 容器。而如果对内存大小比较敏感或者数据存储要求有序的话,则可以用 map 容器。

基本使用

unordered_map 的用法和 map 大同小异,一个简单示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <unordered_map>
#include <string>
int main(int argc, char **argv) {
std::unordered_map<int, std::string> map;
map.insert(std::make_pair(1, "Scala"));
map.insert(std::make_pair(2, "Haskell"));
map.insert(std::make_pair(3, "C++"));
map.insert(std::make_pair(6, "Java"));
map.insert(std::make_pair(14, "Erlang"));
std::unordered_map<int, std::string>::iterator it;
if ((it = map.find(6)) != map.end()) {
std::cout << it->second << std::endl;
}
return 0;
}

使用自定义类

要使用哈希表,必须要有对应的计算散列值的算法以及判断两个值(或对象)是否相等的方法。
在 Java 中,Object 类里有两个重要方法:hashCodeequals 方法。其中 hashCode 方法便是为散列存储结构服务的,用来计算散列值;而 equals 方法则是用来判断两对象是否等价。由于所有的类都继承自 java.lang.Object 类,因此所有类相当于都拥有了这两个方法。

而在 C++ 中没有自动声明这类函数,STL 只为 C++ 常用类提供了散列函数,因此如果想在 unordered_map 中使用自定义的类,则必须为此类提供一个哈希函数和一个判断对象是否相等的函数(e.g. 重载 == 运算符)。下面是一个简单示例(扒自数据结构上机作业的部分代码):

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
using std::string;
using std::cin;
using std::cout;
using std::endl;
using std::unordered_map;
class Person {
public:
string phone;
string name;
string address;
explicit Person() {}
explicit Person(string name, string phone, string address): name(name), phone(phone), address(address) {}
// overload operator==
bool operator==(const Person& p) {
return this->phone == p.phone && this->name == p.name
&& this->address == p.address;
}
inline friend std::ostream& operator<<(std::ostream& os, Person& p) {
os << "[Person] -> (" << p.name << ", " << p.phone << ", "
<< p.address << ")";
return os;
}
};
// declare hash<Person>
namespace std {
template <>
struct hash<Person> {
std::size_t operator()(const Person& p) const {
using std::size_t;
using std::hash;
using std::string;
// Compute individual hash values for first,
// second and third and combine them using XOR
// and bit shifting:
return ((hash<string>()(p.phone)
^ (hash<string>()(p.name) << 1)) >> 1)
^ (hash<string>()(p.address) << 1);
}
};
}
unordered_map<string, Person> phoneMap;
void selectByPhone() {
string phone;
cout << "Input the phone number: "; cin >> phone;
unordered_map<string, Person>::iterator it;
int size = phoneMap.size();
for(int pc = 0; pc < size; pc++) {
if((it = phoneMap.find(phone)) != phoneMap.end()) {
cout << "Query result: " << it->second << endl;
return;
}
}
cout << "Query result : target_not_found" << endl;
}

关于哈希值如何计算,前面我写过一篇文章专门介绍这个:hashCode 方法及 equals 方法的规范

Android 应用性能优化总结

在移动端内存非常宝贵,我们要尽可能地去优化内存以达到最佳性能,并努力地去避免OOM问题。这篇文章总结一些最常见的Android性能优化的一些事项~


图片加载

在移动端,图片的加载往往是最消耗内存的,OOM也经常会发生在加载图片时。以下是加载图片的几个注意事项:

  • 按需要的大小加载。缩略图加载成原图的精细度并不会提升视觉上的效果,但会额外占用不少内存。
  • 图片的缓存使用LruCache,并且合理地设置缓存大小
  • 可以用一些高效的图片加载库,比如Facebook的Fresco

注意一些额外的内存消耗

  • 应特别注意HashMap这个数据结构,必要的时候可以用SparseArray等等的数据结构代替以节省内存
  • 需要频繁修改字符串的地方考虑用StringBuilder代替String
  • 避免创建无用的实例

有限度地使用Service

当我们启动一个Service时,系统会倾向于将这个Service所依赖的进程进行保留,这样就会导致这个进程变得非常消耗内存。并且,系统可以在LRU cache当中缓存的进程数量也会减少,导致切换应用程序的时候耗费更多性能。严重的话,甚至有可能会导致崩溃,因为系统在内存非常吃紧的时候可能已无法维护所有正在运行的Service所依赖的进程了。

因此,控制好Service的生命周期是很重要的。切忌一个无用的Service跑在后台,这会非常影响性能。如果一个逻辑只需要进行一次,那么可以用IntentService代替。

Handler必须为静态内部类

首先复习一下Java几种内部类的语言规范,Java中的inner class(内部类)定义在一个类的内部,它有一个指向外部类的引用。这就有可能导致一个问题,其外部类的生命周期已经结束,而由于inner class持有外部类的引用,并且inner class与其它对象还有引用关联,因此GC进行可达性分析时发现内部类与外部类仍有引用关系,因此不会cause GC,从而导致内存泄露。
static nested class(静态内部类)虽定义在类的内部,但是它不持有外部类的引用,只能访问外部类的静态实例和方法。

在安卓开发中,一个典型的例子是Handler的使用,它会有这样的问题:

In Android, Handler classes should be static or leaks might occur. Messages enqueued on the application thread’s MessageQueue also retain their target Handler. If the Handler is an inner class, its outer class will be retained as well. To avoid leaking the outer class, declare the Handler as a static nested class with a WeakReference to its outer class.

这句话的主旨就是,Handler类必须声明为静态(内部)类(static nested class),否则可能会发生内存泄露。因为,进入MessageQueueMessage会持有它们目标Handler的引用;这就可能出现一种情况,一个消息还在排队,而此时目标Handler类所对应的外部类的生命周期已到onDestroy,即将被GC,但由于目标Handler类仍持有其外部类的引用,使得外部类不能被回收,从而导致内存泄露。这一点说明了Handler类型的对象,生命周期是未知的

然而如果声明为static,又会有许多不方便的地方,比如很多逻辑需要访问外部类的非静态变量和非静态方法。此时,我们应该使用外部类的弱引用(WeakReference),举例表示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
private static class MyHandler extends Handler {
private final WeakReference<DeviceUserFragment> mFragment;
public MyHandler(DeviceUserFragment fragment) {
mFragment = new WeakReference<>(fragment);
}
@Override
public void handleMessage(Message msg) {
super.handleMessage(msg);
Object object = msg.obj;
switch (msg.what) {
case HWServiceConfig.GET_DEVICE_USER_INFO:
mFragment.get().mInfo = (DataUserInfo)object;
mFragment.get().isInfoOK = true;
mFragment.get().updateUI();
break;
default:
break;
}
}
}

这里顺便复习一下JVM中的四种引用的知识吧(直接扒的以前自己的文章):

  • StrongReference(强引用)是最普通的引用类型,只要强引用存在,GC就不会进行垃圾回收。
  • SoftReference(软引用)用来描述一些有用但是非必需的对象。如果一个对象只具有软引用,则内存空间足够,垃圾回收器就不会回收它;如果内存空间不足了,就会回收这些对象的内存。只要垃圾回收器没有回收它,该对象就可以被程序使用。软引用可以和一个引用队列(ReferenceQueue)联合使用,如果软引用所引用的对象被垃圾回收器回收,JVM就会把这个软引用加入到与之关联的引用队列中。软引用可用来实现内存敏感的高速缓存。
  • WeakReference(弱引用)是一种生命周期比软引用更短的引用。当GC扫描启动时,只要扫描到只具有弱引用的对象,无论内存是否够用都会执行GC;但由于GC线程优先级很低,因此并不一定能迅速发现这些弱引用对象。弱引用也可以和一个引用队列联合使用。
  • PhantomReference(虚引用)不同于其余三种引用,虚引用不会影响对象的生命周期,也无法通过虚引用获得对象的一个实例;如果一个对象仅持有虚引用,那么它就和没有任何引用一样,在任何时候都可能被垃圾回收器回收。虚引用主要用来跟踪对象被垃圾回收器回收的活动,它必须和引用队列联合使用。

明白了弱引用的生命周期,此处想必就很好理解了。构造一个外部类的弱引用,然后通过get方法获得其实例进行操作即可,既避免了内存泄露,又可以自由地调用外部类的方法。

WeakReferenceSoftReference 在其他很多地方也都有运用,以后再补充~


参考资料

Android 异步消息处理机制总结

本次项目完成,对安卓的异步消息处理机制有了更深的了解,在这里总结一下。

Prolouge

先来回顾一下基础,Android中的异步消息处理主要由Message, Handler, MessageQueueLooper四部分组成。

Message

Message主要作为线程之间传递的信息,它可以携带一些数据。它的what字段(一般用来表示消息类型)、arg0arg1字段可以携带一些整型数据,obj字段可以携带一个对象,并且可以用setData方法传输一个Bundle对象。

Message的创建方法有两种:

1
2
3
Message msg0 = new Message(); //调用Message的构造方法
Message msg1 = Message.obtain(); //从消息池中获取
Message message = mHandler.obtainMessage(); //或者这样从消息池中获取

其中,HandlerobtainMessage方法也是调用了obtain方法:

1
2
3
4
5
6
7
8
/**
* Returns a new {@link android.os.Message Message} from the global message pool. More efficient than
* creating and allocating new instances. The retrieved message has its handler set to this instance (Message.target == this).
* If you don't want that facility, just call Message.obtain() instead.
*/
public final Message obtainMessage() {
return Message.obtain(this);
}

这两种方法的本质区别是,obtain方法直接从消息池中获取Message对象,这样很多时候可以避免创建新对象,减少内存开销,从obtain方法的源码中就能看出这一点:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
* Return a new Message instance from the global pool. Allows us to
* avoid allocating new objects in many cases.
*/
public static Message obtain() {
synchronized (sPoolSync) {
if (sPool != null) {
Message m = sPool;
sPool = m.next;
m.next = null;
m.flags = 0; // clear in-use flag
sPoolSize--;
return m;
}
}
return new Message();
}

因此,获取Message时尽量使用obtain方法。

Handler

Handler用于发送和处理信息,相当于生产者和消费者。Handler通过sendMessage方法将Message传入MessageQueue消息队列,经Looper轮询后将Message传递至handleMessage方法中。

最常见的一个应用就是需要在子线程中处理UI,这时候就需要借助Handler实现。

MessageQueue

MessageQueue,顾名思义就是消息队列,它用来存放Handler发送的消息,直到消息被处理。每个线程中只能有一个消息队列。

Looper

Looper相当于MessageQueue的监视器。首先调用Looper.loop()方法进入无限循环状态,每当一个新的Message进入MessageQueueLooper就会轮询,将此Message传递给handleMessage方法。每个线程中只能有一个Looper对象。

底层实现

一个标准的异步处理流程应该是这样:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class LooperThread extends Thread {
public Handler mHandler;
public void run() {
Looper.prepare();
mHandler = new Handler() {
public void handleMessage(Message msg) {
// process incoming messages here
}
};
Looper.loop();
}
}

我们从Handler的构造函数开始分析:

1
2
3
public Handler() {
this(null, false);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public Handler(Callback callback, boolean async) {
if (FIND_POTENTIAL_LEAKS) {
final Class<? extends Handler> klass = getClass();
if ((klass.isAnonymousClass() || klass.isMemberClass() || klass.isLocalClass()) &&
(klass.getModifiers() & Modifier.STATIC) == 0) {
Log.w(TAG, "The following Handler class should be static or leaks might occur: " +
klass.getCanonicalName());
}
}
mLooper = Looper.myLooper();
if (mLooper == null) {
throw new RuntimeException(
"Can't create handler inside thread that has not called Looper.prepare()");
}
mQueue = mLooper.mQueue;
mCallback = callback;
mAsynchronous = async;
}

如果我们直接在子线程中创建Handler,会抛出异常,提示 “Can’t create handler inside thread that has not called Looper.prepare()”,也就是要调用Looper.prepare()方法。根据源码,这是因为子线程的Looper为空所致,而观察prepare方法的源码可知,此方法的作用就是创建一个Looper对象:

1
2
3
4
5
6
7
8
9
10
public static void prepare() {
prepare(true);
}
private static void prepare(boolean quitAllowed) {
if (sThreadLocal.get() != null) {
throw new RuntimeException("Only one Looper may be created per thread");
}
sThreadLocal.set(new Looper(quitAllowed));
}

而主线程也没有调用Looper.prepare(),为什么没有崩溃呢?显然是系统自动地帮我们调用了这个方法:

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
public static void main(String[] args) {
SamplingProfilerIntegration.start();
// CloseGuard defaults to true and can be quite spammy. We
// disable it here, but selectively enable it later (via
// StrictMode) on debug builds, but using DropBox, not logs.
CloseGuard.setEnabled(false);
Environment.initForCurrentUser();
// Set the reporter for event logging in libcore
EventLogger.setReporter(new EventLoggingReporter());
Security.addProvider(new AndroidKeyStoreProvider());
// Make sure TrustedCertificateStore looks in the right place for CA certificates
final File configDir = Environment.getUserConfigDirectory(UserHandle.myUserId());
TrustedCertificateStore.setDefaultUserDirectory(configDir);
Process.setArgV0("<pre-initialized>");
Looper.prepareMainLooper();
ActivityThread thread = new ActivityThread();
thread.attach(false);
if (sMainThreadHandler == null) {
sMainThreadHandler = thread.getHandler();
}
if (false) {
Looper.myLooper().setMessageLogging(new
LogPrinter(Log.DEBUG, "ActivityThread"));
}
Looper.loop();
throw new RuntimeException("Main thread loop unexpectedly exited");
}

其中的Looper.prepareMainLooper()方法最后调用了Looper.prepare()方法,创建了主线程的Looper。而子线程则不会主动创建Looper,必须自己调用方法创建。

创建完了Handler,下一步就是创建Message然后sendMessage了:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public final boolean sendMessage(Message msg) {
return sendMessageDelayed(msg, 0);
}
public final boolean sendMessageDelayed(Message msg, long delayMillis) {
if (delayMillis < 0) {
delayMillis = 0;
}
return sendMessageAtTime(msg, SystemClock.uptimeMillis() + delayMillis);
}
public boolean sendMessageAtTime(Message msg, long uptimeMillis) {
MessageQueue queue = mQueue;
if (queue == null) {
RuntimeException e = new RuntimeException(
this + " sendMessageAtTime() called with no mQueue");
Log.w("Looper", e.getMessage(), e);
return false;
}
return enqueueMessage(queue, msg, uptimeMillis);
}

sendMessage的结果是将此Message入队。注意到MessageQueue中只保存了当前待处理的一个对象,而不是一个集合;出队则是由Looper.loop()进行:

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
public static void loop() {
final Looper me = myLooper();
if (me == null) {
throw new RuntimeException("No Looper; Looper.prepare() wasn't called on this thread.");
}
final MessageQueue queue = me.mQueue;
// Make sure the identity of this thread is that of the local process,
// and keep track of what that identity token actually is.
Binder.clearCallingIdentity();
final long ident = Binder.clearCallingIdentity();
for (;;) {
Message msg = queue.next(); // might block
if (msg == null) {
// No message indicates that the message queue is quitting.
return;
}
// This must be in a local variable, in case a UI event sets the logger
Printer logging = me.mLogging;
if (logging != null) {
logging.println(">>>>> Dispatching to " + msg.target + " " +
msg.callback + ": " + msg.what);
}
msg.target.dispatchMessage(msg);
if (logging != null) {
logging.println("<<<<< Finished to " + msg.target + " " + msg.callback);
}
// Make sure that during the course of dispatching the
// identity of the thread wasn't corrupted.
final long newIdent = Binder.clearCallingIdentity();
if (ident != newIdent) {
Log.wtf(TAG, "Thread identity changed from 0x"
+ Long.toHexString(ident) + " to 0x"
+ Long.toHexString(newIdent) + " while dispatching to "
+ msg.target.getClass().getName() + " "
+ msg.callback + " what=" + msg.what);
}
msg.recycleUnchecked();
}
}

出队的逻辑为queue.next(),其逻辑为:如果MessageQueue的待处理消息对象不为空,那么就出队并让下一个消息入队,否则阻塞。消息出队后经由dispatchMessage方法回调,以便在handleMessage中接收到Message并进行处理:

1
2
3
4
5
6
7
8
9
10
11
12
public void dispatchMessage(Message msg) {
if (msg.callback != null) {
handleCallback(msg);
} else {
if (mCallback != null) {
if (mCallback.handleMessage(msg)) {
return;
}
}
handleMessage(msg);
}
}

这就是一个完整的异步消息处理机制,用网上的一幅图总结:

消息处理机制(图片来自网络)

AsyncTask

当然从Android 1.5开始,谷歌就引入了一个更方便使用的AsyncTask类用于处理异步任务,非常轻量级,通过实现其回调函数来实现相应逻辑。比如我写了一个异步读取缓存的Task:

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
private static class CacheTask extends AsyncTask<String, Void, User> {
private final WeakReference<Context> mContext;
private CacheTask(Context context) {
mContext = new WeakReference<>(context);
}
@Override
protected User doInBackground(String... params) {
Serializable object = XmlCacheManager.readObject(mContext.get(), "user");
if (object == null) {
return null;
} else {
return (User) object;
}
}
@Override
protected void onPostExecute(User info) {
super.onPostExecute(info);
if (info != null) {
mContext.get().mInfo = info;
mContext.get().mErrorLayout.setType(AppConstant.HIDE_ERROR_LAYOUT);
} else {
mContext.get().mErrorLayout.setType(AppConstant.NETWORK_ERROR_LAYOUT);
}
mContext.get().updateUI();
}
}

在此逻辑中,doInBackground方法用于执行具体的缓存读取,而onPostExecute方法用于通知UI更新任务的结果(即更新UI)。其实AsyncTask底层也是利用上边的异步消息机制实现的,只不过它封装地非常好,免去了开发者自己写Message和Handler的环节,减少编码量。

粗略看了一下AsyncTask的源码,发现其的底层实现用了各种JUC的东西,以后有时间再研究研究它的源码。

C/C++ 结构体字节对齐

最近在群里看到不少人在讨论结构体字节对齐的问题,就顺便看了看,总结一下。

在C中,计算一个结构体的大小不是简单地将其各成员所占空间的大小相加,而是有特定的规则 - 字节对齐。使用字节对齐的原因有两个,第一是某些平台只能在特定地址访问特定的数据,二是提高数据存取的速度(尽量减少存取次数)。C99标准并没有明确规定内存字节对齐的细节,具体细则应由编译器决定。

这里首先引入对齐参数这一概念,这是结构体字节对齐的一个参考量,对于每种变量的对齐参数,不同编译器实现不同,这里参考网上列出GCC和MSVC两种编译器对应的对齐参数(均为32位):

编译器 对应量 char bool(cpp) short int float double 指针
VC++2015 所占空间 1 1 2 4 4 8 4
VC++2015 对齐参数 1 1 2 4 4 8 4
gcc 4.8.2(linux) 所占空间 1 1 2 4 4 8 4
gcc 4.8.2(linux) 对齐参数 1 1 2 4 4 4 4

编译器还可以设置默认对齐参数,用预编译语句#pragma pack(n)表示,在Windows(32位)下n可取1,2,4,8,默认为8;在Linux(32位)下可取1,2,4,默认为4。

最后,每个变量实际的对齐参数为每个成员变量的对齐参数和编译器的默认对齐参数中较小的一个,比如一个float型变量的对齐参数为4,编译器设定的#pragma pack(8),则此变量实际的对齐参数就为4;对于结构体变量,它的自身对齐参数就为它里面各个变量最终对齐参数的最大值。

结构体字节对齐的原则主要有两点:

  1. 结构体的每一个成员相对结构体首地址的偏移量应该是对其参数的整数倍,如果不满足则补足前面的字节使其满足
  2. 结构体的最终大小应该是其对应参数的整数倍

下面用例子来说明(C++):

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
typedef struct node1 {
} S1;
typedef struct node2 {
int a;
char b;
short c;
} S2;
typedef struct node3 {
char a;
int b;
short c;
} S3;
typedef struct node4 {
int a;
short b;
static int c; //静态变量单独存放在静态数据区
} S4;
typedef struct node5 {
bool a;
S1 b;
short c;
} S5;
typedef struct node6 {
bool a;
S2 b;
int c;
} S6;
typedef struct node7 {
bool a;
S2 b;
double d;
int c;
} S7;
typedef struct node8 {
bool a;
S2 b;
char* c;
} S8;

  • node1为一个空结构体,在C中空结构体的大小为0字节,在C++中空结构体的大小为1字节。
  • node2的内存结构:(4 — 1 — 1(补) — 2),总大小为8字节。
  • node3的内存结构:(1 — 3(补) — 4 — 4),总大小为12字节。
  • node4的内存结构:(4 — 2 — 2(补)),总大小为8字节,注意静态变量被分配到静态数据区,不在sizeof计算的范围内。
  • node5的内存结构:(1 — 1 — 2),总大小为4字节。
  • node6的内存结构:(1 — 3(补) — 8 — 4),总大小为16字节,注意结构体变量的对齐参数的计算。
  • node7的内存结构:(1 — 3(补)— 8 — 4(补) — 8 — 4 — 4(补)),总大小为32字节。
  • node8的内存结构:(1 — 3(补) — 8 — 4),总大小为16字节。

详细分析一下node7,其余的也类似:

  • #pragma pack(n)为8
  • 对于a变量,其对齐参数为1,此时offset=0,可以被1整除,因此为其分配1字节空间;
  • 对于b变量,其对齐参数为4(s2结构体的成员变量最大对齐参数为int => 4),此时offset=1,不能被4整除,因此填充3字节后为其分配8字节空间;
  • 对于d变量,其对齐参数为8,此时offset=12,不能被8整除,因此填充4字节后为其分配8字节空间。
  • 对于c变量,其对齐参数为4,此时offset=24,可以被4整除,因此为其分配4字节空间。
  • 此时所有变量都分配完,但此时offset=28,不能被最大对齐参数8整除,因此填充4字节使其可以被8整除。所以最后node7的大小为32字节。

node7 内存分配