魔改系列-3极速少年带你走一圈

你有种再说一遍

cad魔改多了,今天来改改人吧.目前论坛新手知识面参次不齐,应该说普遍偏低,尤其是lisp区,让他们由浅入深真的太难了,半年多了还没入门的,甚至还有质疑c#的,加上还有一些人喜欢在B站做视频,真是与其提升自己,还不如误人子弟.


《新手论》
新手如何提问:"我想做什么,然后做了什么尝试,发现不行,请问你们怎么做的?"而不是张嘴就问,而不是描述事实:"我不懂".
新手如何反问自己:把自己当成杠精,不断反问自己,"如果我做了步骤不行会如何?然后呢?例外呢?我应该在什么地方找到可能存在的?官方文档有没有?github有没有?bing有没有?"掌握方法论比掌握方法本身更重要(哲学,推眼镜).
新手如何学习:要学就要有步骤学,不要说"学着玩",不然就不要学.不会的名词就去搜搜看,一星期弄懂1个词,一年52个词和背后的原理呢.
新手如何形成逻辑:多做思维导图,多画流程图.
新手应该如何反驳:你得说一个道理出来,并且接受他人的道理,道理不一定对,所以用评分制去判断占比.
对于不讲道理的,一概以大傻春来看待.正所谓成年人不做教育只做筛选.
不要用什么"版本兼容"来阻止你的学习,那是别人阻止你学习的,因为这个世界没有人会觉得你掌握了比他更优秀的知识而开心.
而跨过这个山,还有一片天,如果只愿意看见眼前苟且,降维打击就是我对你做的事情.凡事做到60分就行了,60分是动力的开始,没有多少人是天才.


《巩固基础》
cad开发本质是计算机图形开发,需要了解什么?
你可以什么都不了解,看下去,然后就打个印象先,因为我这是查漏补缺,不是新手教学.
以下内容很多都是lisp转c#会疑惑的.


概念分离是非常重要的,很多人把cad.net二次开发的一些概念和服务端开发给耦合了,例如加入了IOC,实际上IOC是服务端开发的.
cad.net二次开发是客户端开发,应该是面向游戏开发那样,以极限性能优化为核心.你需要减少foreach的使用,能for就for,不少游戏公司禁用foreach就是这个道理.
那应该什么时候使用foreach和linq呢?IO密集型和前台...(偷懒除外)


客户端前台:
async/await是前台才需要的,通过一个监控线程的状态机,实现一个线程的上下文切换实现执行.所以cad上面用它是不能处理数据库层面的任务,会显示上下文错误.


客户端后台:
数据库读写分离,事务的锁粒度控制,CPU密集,SOA内存布局,SIMD,并行任务,多线程.


服务端的一些技能:
池化是提前初始化,延迟初始化是Lazy.
IOC可以类型解耦:
可以通过注入服务来实现应用服务.
不同服务的跨进程通讯,可以利用RPC和消息队列:
同步不解耦,用RPC.异步解耦,用消息队列.




0x01 内存:
栈:
一个方法运行时候会开辟栈帧,一次递归的时候栈帧变量相当于复制了一份,n次就n份,所以说递归容易爆栈,因此我们更喜欢改为循环.注意,它和数据结构的栈不是一回事.
堆:
每次new Class()就是在堆上面,所以你基本上很少遇到爆栈问题,因为c#默认让你在堆里面玩,并且它默认栈帧内存很大.
class是托管类型,每个class是有头结构的,它需要储存GC计数释放,线程号,hash值等,而c#和Java的头还不太一样,这就是为什么多线程编程时,c#需要自己在类上面写new object来lock,而java只需要写synchronized关键字.
既然class有头,那么说明了它不是一个干净的结构,难以转为指针类型,因此和c语言交互就用struct.
释放:
年轻代是标记复制算法,老年代是CMS回收器进行标记清除算法,但是有了G1回收器之后,也不知道c#是否跟进了.而你只需要写好Dispose函数和析构函数.
怎么触发Dispose?
用using,你甚至可以滥用,因为写Dispose的人肯定会处理重复释放问题以及能不能释放的问题.例如每个临时图元都可以加,它的Dispose里面写了if(databse==null)才释放,而你加入数据库它就转移所有权了,就不释放了.
怎么触发析构函数?
用while(true) new class();微软都没有这个触发案例,析构是GC计数满了才去触发的,因此你必须写using,而不是期待析构函数触发.
JIT编译:
为什么很多语言喜欢塞入runtime?因为它有JIT特化,能够在运行时修改指令排序,使得分支命中率提高,峰值性能比AOT更好.也就看到很多c#测试比c++还快的原因.
AOT编译:
启动快,编译后跟c++编译后是一样的了,c#现在已经支持某些win版本,哦～我就喜欢它～
编译器优化:
一定要知道编译器是存在优化模式的,代码写成啥样子得到的优化结果是一样的话,那你为什么不选择好看那个呢?不要以为少写一个变量就跑更快了,例如常量折叠,常量传播,函数内联.




0x02 方法和类设计:
1 函数设计:
1.1 圈复杂度,用来描述一个方法里写很多if和while的复杂度,值越大代表越难懂,不妨把它们拆了,塞到新函数里.
1.2 主函数(命令的方法)是用来控制的,不是用来计算的.所以将计算的拆到新函数里,主函数只留下调用,因此你常看见主函数很多if(flag)return来中断逻辑.
1.3 超级函数,一个函数参数超过4个,那么表示很难懂,这个时候最好是抓几个参数封装成类(CPU在超过4个参数会用栈传递,更慢,软性不强调).
1.4 热点函数,拆开分支到函数才知道这个分支的调用次数,尤其多线程分析,能够在调试器上看到火焰图上面有什么函数被调用时候超多次,此时它就是值得优化的地方.
2 类设计:
2.1 尽量不使用静态类,这样你才知道动态的魅力.
2.2 尽量减少信息熵,一个矩形只有4个double,而不是4个Point3d,更小更快.
2.3 超级类,一个类完成的任务不止一种,破坏单一职责的时候,就要拆成多个类.
2.4 如果你做了一个行为需要不断维护一个类的,那么表示你在违反开闭原则.
2.5 你应该学会讨厌:
a,讨厌被大括号缩进的代码.
b,讨厌信息稀疏的代码.
c,讨厌执行语句出现多次,而可以用分支语句消除的代码.
d,讨厌一行太长的代码.




0x03 数据结构:
数组,链表,hashset,hashmap,红黑树,图(这个倒是很少用,如果世界只有一种结构,那就是图,无圈图就是树,无支树就是链表).
红黑树就是有序结构,而不是用数组储存后需要再进行排序,甚至最低优化就是无脑用已有结构,因为它也非常快!
上面几种结构是最常用的,队列,栈之类可以放一放...但是如果你连迪杰特拉斯双栈算法都没看过,那你可能连计算器都做不出来哦呵呵...
如果你写连基础的数据类型hashmap都不会,那可能会写出R星一样19.8亿次if数.




0x04 事务:
cad本质上是一个单线程数据库管理系统,事务只是用来回滚,它不完全遵守ACID设计,因此我们更为常见是一个命令只有一个事务.结论放在这,必然有例外,例外就是一次性不允许加十万根多段线,会造成句柄溢出,才需要分批,这是cad自身问题,并且这种情况极少.
而使用嵌套事件,那么你终将会碰见平行事务读取,然后傻傻分不清楚,最后得到一个错误.
跨事务情况:跨图必然跨事务,缓存四叉树也存在跨事务,因此传递数据通过id,而不是entity,嵌套事务就会发现entity乱飞,都不知道谁开的entity了,所以事务不是乱开的,只在主流程开(命令),这样才有良好的编程习惯.
事务管理更为详尽说明是mysql数据库,去看看java八股文吧,别一天到头想cad的底层实现了.




0x05 事件:
了解全局事件和局部事件,还有win32api的鼠标钩子和键盘钩子...
一个细节是,不要使用图元删除事件,而是使用文档删除事件去获取图元信息,因为文档事件才能获取时候再打开事务看词典.这就是局部和全局的区别.




0x06 基础类型的算法:
1,不会有人不知道数组需要倒序删除吧
2,不会有人不知道二维数组可以转为一维数组吧,一维数组[长*高+i]就是索引二维数组,你想想看内存是不是只有一维的?所以一维更贴合硬件层面,而乘法器能完成的,你还要二次指令进入另一循环是不是更慢了,这就是数组扁平化.
3,不会有人不知道hashmap最实用是字符串key吧,而且有weakmap来处理value的软引用,这样做缓存在内存不足的时候可以自动放弃不需要的.
4,不会有人不知道距离是圆形判断,直接比较x1-x2,y1-y2是方形判断吧,前者需要除法器(多次迭代),后者只需要加法器,明显加法器更快啊
5,不会有人不知道点消重利用hashset没有什么用吧?不会不知道先x排序再y再z,再倒序删除,这样只需要判断前后两个,已达线性删除速度吧.
不是Point3d的hash没有用,而是作用不大,精准落在同一个浮点数上面概率微乎其微,但是坍缩的方式,要么取整,要么截断,这两种方式都不是很好,0.999999截断是0.99,取整是1,所以取整是对了,但是它没有很快,取整算法就是扔掉小数部分,然后判断小数部分是不是大于0.5,是就+1,所以它也会判断一次浮点数.既然如此,我们不需要把这个判断交给取整,我们把它交给if(abs(x1-x2)<tol).
6,不会不知道碰撞检测可以用上面的消重点方式扩展吧.
7,不会有人不知道时间复杂度只需要记三个吧:
forfor就是O(n^2),常见冒泡.
二分法O(log2(n)),常见二叉树.
array[n]就是O(1),常见hashset,hashmap.
查询时间复杂度取平均期望,这样只需要看看算法接近以上三个哪个,就明白速度怎么样了.
四叉树:四分法O(log4(n)),八叉树:八分发O(log8(n)),实际上三维图元极少,因此cad其实只需要四叉树就能完成绝大部分任务.
快排/堆排:O(nlog(n))




0x07 SOA数据结构扩展:
图形学开发不懂极致效率和CRUD有什么区别?身为一个极速少年,做图形开发都不懂SOA,那么你会被人笑的.
一般常见到结构是AOS(array of struct)
struct Point3d{
  double x;
  double y;
  double z;
}
那么调用时候是array<Point3d>,表示点的集合.
而CPU在运行的时候,由于搬运主存到寄存器时间太慢了,所以它也会把后面一定长度的内存一起读取过来,也就是你只需要x对比,它也会把y和z读取过来,占用了带宽,可以自行搜索CPU预读机制.
因此,我们更多时候采取SOA(struct of array)
struct Point3ds{
  array<double> x;
  array<double> y;
  array<double> z;
}
当你在网络上面搜索一下,会发现这就是CUDA编程耶,那么在cad有啥用呢?破坏了结构又构建结构吗?(新手要懂得追问自己而不是别人)




这就是点消重的结构:
1,重复点去进行hash计算是一个非常严重的错误,因为hash只适合字符串,你不要跟我说double转字符串,严重影响效率的事情,极速少年怎么会做呢.尤其是hash冲突和扩容你采取什么机制扩容?什么机制又能保障效率呢?这就是为什么:可以但不做.
2,点消重一般采取快排+前后对比,时间复杂度平均O(nlogn):快排是O(nlogn)+遍历是O(n),取平均期望就是O(nlogn).但是多次怎么办?变成m*nlogn了?那就只能制造结构了呀.
3,制造这个SOA点集合是有序的,有序是什么?递增.递增有什么用?二分啊!通过二分法找到最近值,然后数组插入在100万点(24MB)也非常快.
啊?为什么数组插入更快呢?不是链表更快吗?
第一,数组插入需要平移内容,但是这个行为有SIMD处理(我当时还想是不是MMU能直接修改).
第二,链表有next指针,并且需要频繁修改指针,这个行为是跳跃访问,而数组插入是顺序访问,会发现(数组插入:链表)=(1:10)测试一万点,甚至java的linkedlist作者自己都说从来没有用过它.
4,不要以为我不知道红黑树,但是点集利用数组更快.
5,如果把double改为float,惊讶的发现任务时间少了一半.
6,善用非托管数组https://www.cnblogs.com/bitzhuwe ... rray-in-csharp.html




SIMD并行:
并行通常用在矩阵乘法,数组交叉运算,数组合并运算等.所以在cad上面使用并行是非常罕见的,基本上可以不考虑使用,主要是常用的都封装了.
CUDA编程上面作用可就大了,主要是渲染需要计算法向量实现光追.继续学习会发现渲染器环节你才知道这个极限优化的魅力,因为这真的太硬核了,尤其是怎么满用寄存器,为了省一个jmp循环,都要自己展开累加.




下一个极速战场是碰撞检测:
碰撞检测算法其实蛮简单的.
方案一,四(八)叉树
它们虽然能够完成任务,但是它们太慢了.随机正态分布的10w图元平均在200毫秒,完全不能接受,放现实里面,都撞车了,还在那递归呢...
方案二,SAP算法
想想看,刚刚点排序采取了什么行为?快排+前后对比.为什么要提及它?因为碰撞检测本质上也是因此扩展而来.
图元包围盒本质上是Rect(上下左右,4个double值,简化为平面好理解,3维就多了个高...千万不要以为它是点构成啊...)
先按照左排序,遍历每个图元x区间(左右)递进O(n),当左右包含图元时候,判断上下是否包含,包含就是碰撞.最终10w图元测试83ms.这里我并没有用SOA结构,主要是当时也不知道.




0x08 开发原则(反话):
拒绝ide提示,拒绝为空类型检查,拒绝开闭原则,拒绝解耦,主打随心所欲,写得开心最重要,并且使用超级函数,使用超级类,多写硬编码,少写注释,这样代码只有上帝和你知道.
不要做单元测试,测试了就是要改的,不如不测试.
不要看别人的设计模式,因为别人都是害你的,好东西肯定藏着掖着不给你.




0x09 学会git:
你连git flow流程都不知道,那么你注定无法想像协作任务是多优秀的做法,你敲敲你的,我敲敲我的,积沙成塔,相互codereview了解他人想法.
你连git diff都不会用,那么你连对比代码差异都不会.




0x0A 优秀的工程:
ifox里面有优秀的事务栈封装,有输入法切换,有剪贴板重构,有拉伸填充边界,这几个杀手级应用.




0x0B 相关问题:
mysql需要了解吗?
需要,尤其是索引组成,这样可以在cad实现索引.以及事务处理,MVCC是怎么实现的.
redis需要了解吗?mongodb需要了解吗?
不太需要,但是可以作为扩展知识面.
分布式事务和分布式锁需要了解吗?
不需要.
图形学目前必然离不开AI,深度卷积神经网络如何了解?
学CNN,最火模型就是YOLOV8.
搜索引擎怎么做?
用Elasticsearch,还有分布式(坛主,拍拍肩)




0x0C 网络:
侧信道攻击:密码全比较再返回,否则有高精度计时攻击.
文件上传漏洞:改用nginx,和linux文件执行权限封堵.
nat网络结构打洞:nat1-3都可以通过中继服务器打洞,nat4是利用域名绑定进行打洞.




0x0D 错误电子反转bit flipping:
错误的电子反转史称计算机玄学,会造成0=1的诡异现象,超新星爆炸,真空涨落,核辐射,大功率Mos管启动,都是导致它出现的原因.最后会导致死机,蓝屏,甚至错误也拦截不了.
为什么提及它?现在的硬盘和网络通讯手机通讯都有它,是信息论里面的不可消除杂讯.
解决方案:
1,电脑设备加铅板减少概率.
2,硬件看门狗和ECC内存,但是CPU层面还是会发生撞击.
3,软件如果错误了就重启,可以利用状态机切换,需要搞两套切换,概率撞概率.
4,某些必要场景上面,传输协议需要加上md5校验,因为tcp的校验和同时发生2位bit反转造成了亚马逊严重事故.
5,了解明汉距离等纠错码,这就是硬盘和二维码的设计实现.
6,三个CPU求值进行三选二,也可以单CPU三个周期,这就是火箭的设计方案.
7,冗余储存,一个程序想在太空跑几十年,怎能保证其中储存位不坏呢?那就是把程序保存几份,每次加载前按行hash计算,进行三选二,并且记录错误行,进行避让.




0x0E 怎么拉慢你的程序?
学会优化了,怎么能不学会拉慢呢?
看到上面数组和链表对比就知道实际上数组才快,数组如何被CPU缓存才快,数组如何矢量化并且用SIMD指令才快.
lisp底层是链表,它的cons是采取了游离指针缓存了末尾,使得批量尾插法更快,nth的采取遍历到指定,所以nth更慢.
c#写foreach比for慢很多的,就是因为状态机.
volatile关键字可以每次都去读主存,令CPU缓存失效.
然后就可以自己实现一个lisp编译器,替换当中的几个函数,博客园搜搜lisp语法分析,它的代码极少,直接就是具体语法树了.再利用c#动态编译就可以生成dll了,甚至编译之后还能避免低版本不支持utf8产生的乱码图层名,但是你都会c#了还做什么lisp编译器啊.

gzxl

敢质疑其他语言的，明经就只有 lisp 者了，我也遇到过。可惜质疑者往往也忘记别人也曾经也学过 lisp，都以为自己学了点lisp就了不起。

你有种再说一遍

greypigeon 发表于 2024-2-5 17:09
赞，一大半看不懂。。

只能指出16进制序号又写成10进制这个问题了。。

我改改改改改改改改

落魄山人

赶紧修电脑回来写代码。。

gdfyhao

没有完全看懂，还需要继续学习

wangsr

谢谢分享。

tiancao100

比如我就是土木工程专业编程最牛B的，上面文章我基本看不懂

bonny

Bao_lai

我惊了，直接带飞c#版块，整活！

菜鸟初来乍到

虽然看不懂，不过感觉好厉害

轮回

又学到一招，

greypigeon

赞，一大半看不懂。。没什么可探讨的

只能指出16进制序号写成10进制这个小问题了。。