沧海一粟

天下事有难易乎?为之,则难者亦易矣;不为,则易者亦难矣。

0%

在 Java 虚拟机的语境下,垃圾指的是死亡的对象所占据的堆空间。这里便涉及了一个关键的问题:如何辨别一个对象是存是亡?

如何判断对象已死

引用计数法(reference counting)

为每个对象添加一个引用计数器,用来统计指向该对象的引用个数。一旦某个对象的引用计数器为 0,则说明该对象已经死亡,便可以被回收了。

具体实现是这样子的:如果有一个引用,被赋值为某一对象,那么将该对象的引用计数器 +1。如果一个指向某一对象的引用,被赋值为其他值,那么将该对象的引用计数器 -1。也就是说,我们需要截获所有的引用更新操作,并且相应地增减目标对象的引用计数器。

缺点:

  1. 需要额外的空间来存储计数器,以及繁琐的更新操作。
  2. 有一个重大的漏洞,那便是无法处理循环引用对象。从而造成了内存泄露。

可达性分析

将一系列 GC Roots 作为初始的存活对象合集(live set),然后从该合集出发,探索所有能够被该集合引用到的对象,并将其加入到该集合中,这个过程我们也称之为标记(mark)。最终,未被探索到的对象便是死亡的,是可以回收的。

阅读全文 »

数组(Array)是一种线性表数据结构。它用一组连续的内存空间,来存储一组具有相同类型的数据。

线性表(Linear List)。顾名思义,线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。其实除了数组,链表、队列、栈等也是线性表结构。

连续的内存空间和相同类型的数据

拿一个长度为 10 的 int 类型的数组 int[] a = new int[10]来举例。

1
2


计算机给数组 a[10],分配了一块连续内存空间 1000~1039,其中,内存块的首地址为 base_address = 1000。
计算机会给每个内存单元分配一个地址,计算机通过地址来访问内存中的数据。当计算机需要随机访问数组中的某个元素时,它会首先通过下面的寻址公式,计算出该元素存储的内存地址:a[i]_address = base_address + i * data_type_size其中 data_type_size 表示数组中每个元素的大小。我们举的这个例子里,数组中存储的是 int 类型数据,所以 data_type_size 就为 4 个字节。

阅读全文 »

数据结构和算法本身解决的是“快”和“省”的问题,即如何让代码运行得更快,如何让代码更省存储空间。所以,执行效率是算法一个非常重要的考量指标。

(1) 为什么需要复杂度分析

把代码跑一遍,通过统计、监控,就能得到算法执行的时间和占用的内存大小。为什么还要做时间、空间复杂度分析呢?

这种评估算法执行效率的方法是正确的,叫事后统计法。但是,这种统计方法有非常大的局限性。

  1. 测试结果非常依赖测试环境
  2. 测试结果受数据规模的影响很大

在大学刚学C语言的时候,老师交给我们一个任务,根据高斯公式计算π的值,分别精确到第六位、第七位、第八位 …,下课后直接在图书馆写代码计算,计算结果精确到第六位的时候特别快,刚点运行就计算完了,花费几ms,计算第七、八、九位也很快,不超过3s,但是精确到第十位的时候,运行了30s后,听到电脑风扇 呼呼 地响了。

阅读全文 »

The Structure of the Java Virtual Machine

  1. The class File Format
  2. Data Types
  3. Primitive Types and Values
  4. Reference Types and Values
  5. Run-Time Data Areas
  6. Frames
  7. Representation of Objects
  8. Floating-Point Arithmetic
  9. Special Methods
  10. Exceptions
  11. Instruction Set Summary
  12. Class Libraries
  13. Public Design, Private Implementation

  本文档指定了一台抽象机器。它没有描述Java虚拟机的任何特定实现。

  要正确实现Java虚拟机,您只需要能够读取类文件格式并正确执行其中指定的操作。不属于Java虚拟机规范的实现细节将不必要地限制实现者的创造力。例如,运行时数据区域的内存布局、使用的垃圾收集算法以及Java虚拟机指令的任何内部优化(例如,将它们转换为机器代码)都由实现者自行决定。

  本规范中对Unicode的所有引用都是针对Unicode标准6.0.0版提供的,可从http://www.unicode.org/。

阅读全文 »