学计算机的那个

不是我觉到、悟到，你给不了我，给了也拿不住;只有我觉到、悟到，才有可能做到，能做到的才是我的.

0%

发表于 更新于 分类于

二叉查找树（Binary Search Treee），也称二叉搜索树，是指一课空树或者具有下列性质的二叉树：

  1. 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
  2. 若任意节点的右子树不空，则右子树上所有节点的值均大于或等于它的根节点的值；
  3. 任意节点的左、右子树也分别为二叉搜索树；

二叉搜索树相比其他数据结构的优势在于查找、插入的时间复杂度较低。为O（log n）

阅读全文 »

发表于 更新于 分类于

快速排序

  1. 从数列中挑出一个元素，称为 “基准”（pivot）;
  2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
  3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；
阅读全文 »

发表于 更新于 分类于 ，

如何处理带有property的Protol

1
2
3
4
5
6
7
8
9
10
11
@protocol MyProtocol <NSObject>

@required

@property (readonly) NSString *title;

@optional

- (void) someMethod;

@end
阅读全文 »

发表于 更新于 分类于 ，
变量类型 是否捕获到 block 内部 访问方式
全局变量 否 直接访问
局部变量（auto 类型） 是 值传递
局部变量（static 类型） 是 指针传递
阅读全文 »

发表于 更新于 分类于 ，

几个关于block的问题

  • block的内部实现，结构体是什么样的
  • block是类吗，有哪些类型
  • 一个int变量被 __block 修饰与否的区别？block的变量截获
  • block在修改NSMutableArray，需不需要添加__block
  • 怎么进行内存管理的
  • block可以用strong修饰吗
  • 解决循环引用时为什么要用__strong、__weak修饰
  • block发生copy时机
  • Block访问对象类型的auto变量时，在ARC和MRC下有什么区别
阅读全文 »

发表于 更新于 分类于

这是一次失败的安装，起因是前几天面试被问到，有没有用过iDA这个工具

阅读全文 »

发表于 更新于 分类于 ，

虚拟内存和物理内存

计算机组成原理里可知，32位CPU对应32位OS，它的寻址空间是2的32次方，约为4GB，意味着在32位的计算机系统中，理论支持的物理最大寻址空间是4GB。

1
32位CPU只有32根地址总线，所以最大的寻址能力是2的32次方
阅读全文 »

发表于 更新于 分类于 ，

一道面试题

1
2
3
4
5
NSInteger i = 0xFFFFFFFFFFFFFF;
//NSInteger i = 1;
NSNumber *number = [NSNumber numberWithInteger:i];
NSLog(@"%zd", malloc_size((__bridge const void *)(number))); // 32
NSLog(@"%zd", sizeof(number)); // 8

由于NSNumber继承自NSObject，所有它有isa指针，加上内存对齐的处理，系统给NSNumber对象分配了 32 个字节内存。通过 LLDB 指令读取它的内存，实际上它并没有用完 32 个字节。

Tagged Pointer

iPhone 5s开始采用64bit cpu架构，也就是指针占用4个字节，32bit的寻址范围是4G，显然64bit的指针存在空间浪费，对于小对象，比如NSNumer，NSDate，NSString，TaggeddPointer不再是地址，而是真正的值。这种方式可以节省内存，提高执行效率

引入 Tagged Pointer 技术之后NSNumber等对象的指针中存储的数据变成了Tag+Data形式（Tag为特殊标记，用于区分NSNumber、NSDate、NSString等对象类型；Data为对象的值）。这样使用一个NSNumber对象只需要 8 个字节指针内存。当指针的 8 个字节不够存储数据时，才会在将对象存储在堆上。

实现分析

1
2
3
4
5
6
7
8
9
10
11
- (void)viewDidLoad {
    [super viewDidLoad];
               
    NSNumber *number1 = @1;
    NSNumber *number2 = @2;
    NSNumber *number3 = @79;
    NSNumber *number4 = @(0xFFFFFFFFFFFFFFFF);
    
    NSLog(@"%p %p %p %p", number1, number2, number3, number4);   
}
// 0xb000000000000012 0xb000000000000022 0xb0000000000004f2 0x600000678480

number1～number3指针为Tagged Pointer类型，可以看到对象的值都存储在了指针中，对应倒数第二位开始的1、2、4f。而number4由于数据过大，指针的8个字节不够存储，所以在堆中分配了内存。

最后一位用来表示数据类型。

第一位b的二进制为1011，其中第一位1是Tagged Pointer标识位。后面的011是类标识位，对应十进制为3，表示NSNumber类。
下图是iOS下NSNumber的Tagged Pointer位视图

相关题目

1
2
3
4
5
6
7
8
@property (nonatomic, strong) NSString * name;

dispatch_queue_t queue = dispatch_get_global_queue(0, 0);
for (int i = 0; i < 1000; i++) {
    dispatch_async(queue, ^{
        self.name = [NSString stringWithFormat:@"abcdefghij"];
    });
}
1
2
3
4
5
6
7
8
@property (nonatomic, strong) NSString * name;

dispatch_queue_t queue = dispatch_get_global_queue(0, 0);
for (int i = 0; i < 1000; i++) {
    dispatch_async(queue, ^{
        self.name = [NSString stringWithFormat:@"abcdefghi"];
    });
}

第一段代码Crash，而第二段却没有问题。
分别打印两段代码的self.name类型看看，原来第一段代码中self.name为__NSCFString类型，而第二段代码中为NSTaggedPointerString类型。

__NSCFString存储在堆上，它是个正常对象，需要维护引用计数的。self.name通过setter方法为其赋值。而setter方法的实现如下：

1
2
3
4
5
6
7

- (void)setName:(NSString *)name {
    if(_name != name) {
        [_name release];
        _name = [name retain]; // or [name copy]
    }
}

异步并发执行setter方法，可能就会有多条线程同时执行[_name release]，连续release两次就会造成对象的过度释放，导致Crash。

解决办法：

  1. 使用atomic属性关键字。
  2. 加锁
1
2
3
4
5
6
7
8
9
 @property (atomic, strong) NSString * name;
dispatch_queue_t queue = dispatch_get_global_queue(0, 0);
for (int i = 0; i < 1000; i++) {
    dispatch_async(queue, ^{
        // 加锁
        self.name = [NSString stringWithFormat:@"abcdefghij"];
        // 解锁
    });
}

第二段代码中的NSString为NSTaggedPointerString类型，在objc_release函数中会判断指针是不是TaggedPointer类型，是的话就不对对象进行release操作，也就避免了因过度释放对象而导致的Crash，因为根本就没执行释放操作。

1
2
3
4
5
6
7
8
__attribute__((aligned(16), flatten, noinline))
void 
objc_release(id obj)
{
    if (!obj) return;
    if (obj->isTaggedPointer()) return;
    return obj->release();
}

isa指针（NONPOINTER_ISA）

  • 非指针型isa：值的部分代表class地址
  • 指针型isa：值代表class地址

非指针型isa

同理64位存储一个内存地址是种浪费，isa是一个公用体结构union，NONPOINTER_ISA是给对象分配了内存空间，但是不使用sideTable管理引用计数，而是把引用计数存在了isa当中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
union isa_t 
{
    isa_t() { }
    isa_t(uintptr_t value) : bits(value) { }

    Class cls;
    uintptr_t bits;

     struct {
        uintptr_t indexed           : 1;//0表示普通的isa,1表示使用优化的存储引用计数
        uintptr_t has_assoc         : 1;//对象是否包含associated object
        uintptr_t has_cxx_dtor      : 1;//该对象是否有 C++ 或 ARC 的析构函数
        uintptr_t shiftcls          : 44; // MACH_VM_MAX_ADDRESS 0x7fffffe00000   类的指针
        uintptr_t magic             : 6;//固定值为 0xd2，用于在调试时分辨对象是否未完成初始化
        uintptr_t weakly_referenced : 1;//该对象是否有过 weak 对象
        uintptr_t deallocating      : 1;//该对象是否正在析构
        uintptr_t has_sidetable_rc  : 1;//是否使用了引用计数表sideTable
        uintptr_t extra_rc          : 8;//存储引用计数值减一后的结
    };
    ……
};

指针型isa

SideTable包含了引用计数表，弱引用计数表，以及一个自旋锁。结构如下

1
2
3
4
5
6
struct SideTable {
    spinlock_t slock;
    RefcountMap refcnts;
    weak_table_t weak_table;
    ……
}
  • 引用计数表

是用hash表实现的，引用计数会存在多张sideTable中，修改引用计数，需要经过两次hash算法，第一次是从sideTables中找到具体的sideTable，第二次是从sideTable中找到对应的引用计数。之所以设计成多张sideTable而不是一张sideTables，是因为每次操作都需要加锁，减锁操作，多张可以分离锁，加快操作速度。

1
2
3
SideTable &table = SideTables()[this];
size_t &refcntStorage = table.refcnts[this];
//refcntStorage  就是引用计数 两次hash查找
  • 弱引用表

苹果使用sideTables保存所有的weak引用，key就是对象地址，weak_entry_t作为值，weak_entry_t中保存了所有指向该对象的弱引用。

1
2
3
4
5
6
struct weak_table_t {
    weak_entry_t *weak_entries;
    size_t    num_entries;
    uintptr_t mask;
    uintptr_t max_hash_displacement;
};

总结

目前OC管理内存的方式有两种Taged Pointer 和 isa指针

参考

Tagged Pointer

发表于 更新于 分类于 ，

一道面试题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
@interface ViewController : UIViewController
@property (nonatomic, strong) NSString *string1;
@property (nonatomic, weak) NSString *string2;
@end


@implementation ViewController
- (void)viewDidLoad {
    [super viewDidLoad];
    // Do any additional setup after loading the view.
        
    [self testKeyword];
}

-(void)testKeyword {
    self.string1 = [[NSString alloc] initWithUTF8String:"string 1"];
    self.string2 = self.string1;
    self.string1 = nil;
    NSLog(@"String 1 = %@",self.string1);
    NSLog(@"String 2 = %@", self.string2);
}
@end
阅读全文 »