安卓平台下面开发DSP应用

这两天考察在手机上面写DSP应用的可能性,找了一些资料读了,有这些困难:

安卓平台:
谷歌有一个叫Oboe的C++库帮助开发音频APP,但是官方文档只提供了一些简单的例子,没有给出类似效果器之类有复杂数学运算的例子。我担心很多DSP运算的实时性得不到保证。

得有DSP芯片的配合才能写出高效的DSP算法,虽然 arm CPU集成有DSP芯片,但是要充分利用DSP的指令,得用arm的付费编译器,据说挺贵的。而且,如果用DSP的指令优化算法,

安卓碎片化的问题有更多的坑。如果用了非常底层的代码(直接写死了DSP的指令),代码在不同的机器上可能表现很不一样,很可能有些机器跑不起来。

一篇2014年的技术文章 https://www.androidauthority.com/state-audio-android-414978/ 讲在android平台下面开发DSP的应用很困难。虽然是7年前的文章,但也很有参考价值。

苹果iOS:
苹果对DSP有很好的支持,但是我没有Mac电脑也没有iphone手机,没办法做开发。

不过,有一个superepowered的开源库,声称完美提供了开发DSP的能力。但是这个库不是完全免费的。官网上也没有明确价格,需要Contact sales。 https://superpowered.com/pricing
那算了,没太大兴趣了解。

用琴生(Jensen)不等式证明期望最大值(EM)算法收敛

今年二月份刷了一遍“机器学习白板推导”系列视频。https://www.bilibili.com/video/BV1aE411o7qd 。这个机器学习的公式推导系列讲地真是太好了,当时像追剧一般花了两个星期听完。非常感谢录这个视频系列的老师shuhuai008。不过,因为以前机器学习的基础几乎为0,又没有动手做相关练习。三个半月以后,又忘了很多了。昨天,我想起要复习一下EM算法,于是又把视频捡起来找到EM算法的部分,复习一下。

第二次看,果然快了很多。不过,在用琴生不等式证明EM算法收敛的部分,卡住了。我不断回忆第一次看的时候是如何理解的,奈何回忆不起来了。于是,找到Jensen不等式的词条看了看,琢磨了好久。终于懂了,在这里把这个思考过程记下来。

我卡在这个步骤:需要用Jensen Inequality证明如下不等式:
\(
\int\limits_z P(z|x, \theta^{(t)}) \log_{}{\frac{P(z|x, \theta^{(t+1)})}{P(z|x, \theta^{(t)})} } dz \le 0
\)
上面公式中的z表示模型中的隐变量,x表示观测值,$ \theta $是参数,$ \theta^{(t)} $表示theta在第t时刻的值(EM算法是一个迭代算法)。

证明这个不等式需要用到琴生不等式在凹函数上的性质。如下:
设f(x)中一个凹函数(凹函数图形和中文字凹的形状相反,可以理解为上凸,log函数即一个凹函数),下面的不等式成立。
$$
a_1f(x_1) + a_2f(x_2) + \dots + a_nf(x_n) \le f(a_1x_1 + a_2x_2 + \dots + a_nx_n)
且 a_1 + a_2 + \dots + a_n = 1
$$
用自然语言描述是:凹函数定义域内的n个自变量对应的因变量的线性组合小于或等于n个自变量先做线性组合再求对应的因变量,作线性组合的系数之和为1。简单地说:先求函数值再做线性组合 小于或等于 先做线性组合再求函数值。

再回到我们要证明的不等式。积分号即可看成是无穷多个值的线性组合,对数符号log后面对应的那一坨
$$ {\frac{P(z|x, \theta^{(t+1)})} {P(z|x, \theta^{(t)})} } $$
看成是log函数的因变量,log前面的
$$
P(z|x, \theta^{(t)})
$$
看成是线性组合的系数,很明显这个系数是满足积分和为1的概率密度。于是,就可以套用上面提到的凹函数上的琴生不等式。不等式的右边为0,左边是“先求函数值再做线性组合”,化简为左边小于“先做线性组合再求函数值”:
$$
\begin{aligned}
左边 &\le log_{}{\int\limits_z {\frac{P(z|x, \theta^{(t+1)})} {P(z|x, \theta^{(t)})} } P(z|x, \theta^{(t)})}dz \&=log_{}{}\int \limits_zP(z|x,\theta^{(t+1)})dz=log_{}{1}=0
\end{aligned}
$$
得证!

使用tailwindcss创建一个全屏模式对话框

最开始用的css UI库是最常用,历史最悠久的bootstrap。 后来又接触了bulma,bulma也做得很漂亮,不过我没有把bulma用在实战中。前段时间打算改版我的粤语网站https://ykyi.net, 调研了多种技术方案,最终选中了nextjs。读nextjs官方文档时发现tailwind是nextjs默认配好的css库。这是第一次接触到tailwindcss。较之Bulma和bootstrap这些UI库给了开箱即用的很多控件,tailwind只是提供了很多css工具(css类),用户需要用这些工具自己创建最终使用的控件。一开始会让人有点畏惧,实际使用之后,其实完全自己创建美观的UI控件也并非有那么困难。

今天用tailwind做了一个全屏的模式对话框Modal Dialog。代码实际上是从网上抄下来的。天下代码我抄你,你抄我嘛~~
HTML代码如下。

<div className="bg-gray-200 flex items-center justify-center h-screen">
    <button className="modal-open btn btn-green">Open Modal</button>

  <div className="modal opacity-0 pointer-events-none fixed w-full h-full top-0 left-0 flex items-center justify-center">
    <div className="modal-overlay absolute w-full h-full bg-gray-900 opacity-50"></div>

    <div className="modal-container bg-white w-11/12 md:max-w-md mx-auto rounded shadow-lg z-50 overflow-y-auto">
      <div className="modal-content py-4 text-left px-6">
        <div className="flex justify-between items-center pb-3">
          <p className="text-2xl font-bold">Simple Modal!</p>
          <div className="modal-close cursor-pointer z-50">
            <svg className="fill-current text-black" xmlns="http://www.w3.org/2000/svg" width="18" height="18" viewBox="0 0 18 18">
              <path d="M14.53 4.53l-1.06-1.06L9 7.94 4.53 3.47 3.47 4.53 7.94 9l-4.47 4.47 1.06 1.06L9 10.06l4.47 4.47 1.06-1.06L10.06 9z"></path>
            </svg>
          </div>
        </div>

        <p>Modal content can go here</p>
        <p>...</p>
        <p>...</p>
        <p>...</p>
        <p>...</p>

        <div className="flex justify-end pt-2">
          <button className="btn btn-green m-2">Action</button>
          <button className="modal-close btn btn-green m-2">Close</button>
        </div>

      </div>
    </div>
  </div>

对应的Javascript代码如下:

var openmodal = document.querySelectorAll('.modal-open')
for (var i = 0; i < openmodal.length; i++) {
openmodal[i].addEventListener('click', function(event){
event.preventDefault()
toggleModal()
})
}

var overlay = document.querySelector('.modal-overlay')
overlay.addEventListener('click', toggleModal)

var closemodal = document.querySelectorAll('.modal-close')
for (var i = 0; i < closemodal.length; i++) {
closemodal[i].addEventListener('click', toggleModal)
}

document.onkeydown = function(evt) {
evt = evt || window.event
var isEscape = false
if ("key" in evt) {
isEscape = (evt.key === "Escape" || evt.key === "Esc")
} else {
isEscape = (evt.keyCode === 27)
}
if (isEscape && document.body.classList.contains('modal-active')) {
toggleModal()
}
};


function toggleModal () {
const body = document.querySelector('body')
const modal = document.querySelector('.modal')
modal.classList.toggle('opacity-0')
modal.classList.toggle('pointer-events-none')
body.classList.toggle('modal-active')
}

让我有点吃惊的时,模式对话框并非使用display:hide达到隐藏的效果。而是使用opacity:0(tailwind的opacity-0类),即不使用模式对话框时,模式对话框在一个全透明的div里面,达到隐藏的效果。当需要展示的时候,删除opacity-0类,即完全不透明,此时模式对话框就展示出来了。

Tailwind这个css工具库还是不错!多用了几次以后,我觉得可以抛弃bootstrap了。想要一个什么UI控件的时候,用tailwind加控件名搜索一下,已经有网友贡献了现成的代码。拿过来理解以后,更方便定制。

讲讲为什么要用javascript的requestAnimationFrame函数在web上实现复杂动画效果

简单地讲,requestAnimationFrame函数更适合在浏览器上面做复杂的动画。比用定时器效率高。

废话如下:

现代的WEB世界(2020年),网页上各种各样的内容丰富多彩。虽然css也能完成很多简单的动画,但是仍然有一些复杂的动画animation需求需要javascript处理。之前,我简单地理解,浏览器已经有定时器函数setTimeout()和setInterval(),就足够做出复杂的动画形式。原来,不是这样的。

这段时间在做一个运行在浏览器上的红白机模拟器,参考开源代码,发现用的是requestAnimationFrame()函数。于是,查了一些资料,涨了知识。

首先,使用定时器SetTimeout和setInterval做动画有两个大缺点。

  1. 受有限的资源,或者糟糕的cpu密集的业务代码的影响。浏览器并不严格按照定时器函数中的时间间隔参数来调度定时回调函数。比如50ms,有时会快,有时会慢。这样,动画效果的帧与帧之间的画面就不会那么流畅了。
  2. 频繁的调用计时器函数setTimeout或setInterval,可能导致浏览器假死。浏览器竭尽全力的处理一些跟动画无关的代码,比如文档流的不断重排。这样,用户的界面根本没有获得重新渲染的机会。特别在手机浏览器,由于手机的环境比较特殊。手机的电池可以不够,网络不好,都可能影响web页面的文档重排(page reflow)的效率。

为什么用requestAnimationFrame

  1. 针对定时器的缺点1,浏览器的实现保证requestAnimationFrame设定的回调函数会严格定时执行。当然是在web页是活跃状态,即不是在后台运行。等下会讲到后台执行时的情况。一般浏览器调用requestAnimationFrame设定的回调函数的频率是每秒60次。不同浏览器的实现有不变。

  2. 当web页面被放入后台运行时,浏览器会大辐降低requestAnimationFrame设置的回调函数调用频率。低至每秒两次,甚至暂停。这样,又能节省相当多的资源。比如手机上珍贵的电池资源。非常容易理解,web页面不可见的时候,还继续渲染画面是完全没有意义的。

需要注意的地方

既然requestAnimationFrame的调用频率因浏览器而异,另外页面在后台时又可能会暂停。所以,生成动画的代码不能预设回调函数以某一个固定的频率执行。解决这个问题,requestAnimationFrame的回调函数会传入一个时间戳参数,

下面是官方文档对传入回调函数的时间参数的解释,给了一个高精度的时间戳,单位是毫秒。嗯,对于浏览器来说,如果能精确到毫秒的话,算得上高精度的时间戳了。

The callback function is passed one single argument, a DOMHighResTimeStamp similar to the one returned by performance.now(), indicating the point in time when requestAnimationFrame() starts to execute callback functions

Tokio简介

什么是Tokio

Tokio是一个事件驱动的运行时(官网用词runtime),用来编写rust异步代码。所谓异步代码,即和同步代码对应而言。比如同步读磁盘上的文件:应用代码调用读文件的函数,函数封装了操作系统的系统调用,通知操作系统读入文件内容,操作系统把文件内容全部读出后才回到应用代码,继续执行之后的逻辑。在操作系统读文件内容的过程中,应用程序无所事事,默默地等待。而异步读入文件内容,异步调用通知操作系统读文件后立即返回,应用程序有机会在操作系统读文件时干其他事情,当操作系统读完文件内容后会以某种形式通知应用程序读文件已经完成

Tokio为异步编程提供了这些东西:
1. 一些基本工具。比如同步原语(synchronization primitives),管道(channels),计时器,延时,intervals(不知道这是什么东西,描述一个时间间隔么?)。
2. API。网络相关的tcp,udp异步函数,异步文件操作函数,异步的进程和信号管理。
3. 调度器,用来调度tasks(类似其他语言的异步框架的绿色线程或协程的概念)。
4. I/O驱动(官网用语IO driver),使用原生操作系统的事件队列接口。比如:linux下的epoll,freeBSD下的kqueue,windows下的IOCP。
5. 高性能的计时器。

快速 Fast

Tokio使用的是Rust编程语言,当然有资格有能力做到快速。Tokio要设计时也把速度放在非常重要的位置。

零开销抽象 Zero-cost abstractions

Tokio广泛使用Future这个异步概念(类似node.js中的promise,据我理解,不同语言的异步框架中使用的future和promise是非常近似的概念)。官方文档声称tokio的future和其他语言的future实现不一样。它是独一无二的(unique)。Tokio中的future会被编译器编译成一个状态机。做异步事件的同步处理时,分配内存,及其他future的实现中有开销的地方,tokio都是零开销。(我觉得协程类的异步框架都要维护状态机用来记录栈的信息么,状态机并不unique。unique的是零开销抽象)。

零开销抽象并不意味着tikio自身没有开销,而指是不可能再用其他什么方法减少开销,开销已经减到最少。

并发 Concurrency

Tokio提供了一个多线程,work-stealing(不知用哪个中文合适)的调度器。Tokio是开箱即用的,意味着,当你使用tokio运行时的时候,你就可能充分利用电脑上所有的cpu核心。

现代计算机通过增加中央处理器的核心来增加性能。所以,能够利用好多核心对于高性能的应用来说是至关重要的。

非阻塞I/O Non-blocking I/O

tokio使用操作系统原生的多路复用技术(linux的epoll,freeBSD的kqueue,windows的IOCP),一个线程可以同时管理多个socket。这样能减少系统调用(system call),提高应用的性能。

可靠 Reliable

Tokio在设计时就竭尽所能避免应用程序因使用tokio不当产生BUG,但tokio当然不可能完全做到这点。Tokio的API设计得不易于用错。这样,在项目的最后一天,你就可以信心满满地交付了。

所有权和类型系统 Ownership and type system

Tokio籍由Rust语言特有的所有权系统和严格的类型安全,能避免很多内存安全方面的错误。它能避免绝大多数常见的内存出错:访问未初始化内存,访问释放后内存,内存重复释放(Double Free)。并且,做到这些并不需要付出运行时的额外开销。(回忆自己用C/C++写的复杂应用时追踪偶发的内存出错BUG真是无比痛苦。)

另外,严格的类型安全系统也使得难以错误使用API。比如,Tokio中的互斥锁并不需要开发者显式释放。(这一点并不稀奇,C++的RAII,Go的defer,python的with也能做到,稍微现代的语言都有类似机制。)

反向压力传递 Backpressure

Tokio自带了压力反向传递的功能,这真是真是一个让人称赞的功能,真香。所谓反向压力传递,可以这么理解:当消费者消费的速度小于生产者生产的速度时,数据会在内存中越堆越多,最终把内存撑暴。反向压消费力传递指的是,消费者的压力会反向传递给生产者,让生产者减慢生产的速度以匹配消费者的消费速度。很多其他的库并没有提供这个功能,于是应用需要自己实现一个。但要实现一个高性能的类似功能并不是一件容易的事情。(回忆起自己有段时间用C++的asio异步网络库写的服务器。我的实现是当存放任务的队列到达一个阈值时就让生产者线程sleep很短一段时间,再从网络中读取数据,生产任务,结果性能大降。我相信tokio一定优雅高效地提供了这个功能。)

tokio官方文档中表示,Tokio中的生产者天生是lazy的,它们会轮循消费者,只有当消费者充许增加数据时,生产者才生产数据。

取消 Cancellation

应用的业务代码持有一个future,它描述了异步计算的结果。如果当业务代码认为并不需要这个结果时,则可以不再持有这个future(让它的生命期结束)。这样,异步计算就会及时结束,不再执行不必要的计算。官方文档表示这主要受益于Tokio的轮循设计。

多谢了Rust的权限模型,异步执行部分能通过实现drop这个特征(trait,类似c++,c#,java的接口),及时感知到future已经被丢弃了。

轻量级 Lightweight

Tokio的伸缩性很好,且伸缩时不给应用增加额外负担。这样,tokio能在资源受限的环境下发展得不错。

没有垃圾回收 No garbage collector

tokio使用的是rust语言,所有没有垃圾回收机制,也就避免了在有垃圾回收的语言中普遍存在的“世界暂停”问题。应用会周期性的启动垃圾回收,在极限性能要求的情况下,这个问题就会暴露出来。Tokio的这个特性使得它适合中实时环境中使用。

模块化 Modular

尽管Tokio提供了非常多开箱即用的功能,并且是用模块式的方式组织的。每一个component都使用一个独立的库library。用户可以精确的设定需要使用哪些特性而只导入相应的库,其他不需要使用的库则不会被编译进最终的应用程序中。很多其他著名的rust库也使用了tokio,比如hyper和actix。

Rust语言的宏编程极简教程Macro

Rust的宏和c/c++的异同

Rust语言的宏设计得比较复杂,当然也可以说功能非常强大,跟c/c++语言的宏非常不一样。
相同点 当然是宏能够让代码更精简,码农可以少敲很多样板代码(boilerplate code)。当然你说函数和类不也可以抽象代码,使代码精简吗?但宏能够获取很多在编译期的信息,函数和类却不能。比如,代码所在的文件和行数,这个信息只有宏才能获得。
不同点 是,C/C++的宏只是在预编译期简单地做模式替换,预编译后再交由编译器。c/c++的include头文件展开也是在预编译阶段。但Rust宏的展开不是发生在预编译期,而是编译期。于是Rust能够获得更复杂的更详细的编译器的信息。这里有两个概念Token Tree和AST。如果有大学阶段学习过的编译原理课程的背景就很容易理解。

Token Tree

Token Tree简写成TT。编译器拿到源代码后先做词法分析,即把源代码字节流分成一个一个的token。token和token之间的逻辑关系也记录下来。比如下面的一个简单语句:

a + b + (c + d[0]) + e

的Token Tree就长这个样子:

«a» «+» «b» «+» «(   )» «+» «e»
         ╭────────┴──────────╮
          «c» «+» «d» «[   ]»
                       ╭─┴─╮
                        «0»

AST

AST的全称是Abstract Syntax Tree,抽象语法树。编译器把Token Tree翻译成AST,这是一个更有利于编译器理解源代码的结构。上面的TT翻译成对应的AST后长这个样子:

              ┌─────────┐
              │ BinOp   │
              │ op: Add │
            ┌╴│ lhs: ◌  │
┌─────────┐ │ │ rhs: ◌  │╶┐ ┌─────────┐
│ Var     │╶┘ └─────────┘ └╴│ BinOp   │
│ name: a │                 │ op: Add │
└─────────┘               ┌╴│ lhs: ◌  │
              ┌─────────┐ │ │ rhs: ◌  │╶┐ ┌─────────┐
              │ Var     │╶┘ └─────────┘ └╴│ BinOp   │
              │ name: b │                 │ op: Add │
              └─────────┘               ┌╴│ lhs: ◌  │
                            ┌─────────┐ │ │ rhs: ◌  │╶┐ ┌─────────┐
                            │ BinOp   │╶┘ └─────────┘ └╴│ Var     │
                            │ op: Add │                 │ name: e │
                          ┌╴│ lhs: ◌  │                 └─────────┘
              ┌─────────┐ │ │ rhs: ◌  │╶┐ ┌─────────┐
              │ Var     │╶┘ └─────────┘ └╴│ Index   │
              │ name: c │               ┌╴│ arr: ◌  │
              └─────────┘   ┌─────────┐ │ │ ind: ◌  │╶┐ ┌─────────┐
                            │ Var     │╶┘ └─────────┘ └╴│ LitInt  │
                            │ name: d │                 │ val: 0  │
                            └─────────┘                 └─────────┘

AST图有排版有点乱,我懒得改了。这两人个图,TT和AST都是从 https://danielkeep.github.io/tlborm/book/mbe-syn-source-analysis.html 抄来的。您可以移步到那个页面。
重点来了,Rust语言的宏展开就发生在编译器生成了源代码的AST的时候。Rust语言的宏可以从AST获得非常丰富的信息,并操作AST。

Rust的宏有两种

Rust语言设计了两种宏,一种叫Declarative Macros(声明式宏),以前的版本也有Macros by example这个名字,旧的名字怪怪的。另一种是Procedure Macros(过程宏)我不明白为什么取这个名字。Declarative Macro相对Procedure Macros要简单一些,而过程宏则可以玩出另复杂的花样。

Declarative Macro

常见的这样一个定义vector的Rust语句:

let v: Vec<u32> = vec![1, 2, 3];

就使用了声明式宏。这个宏的定义如下:

#[macro_export]
macro_rules! vec {
    ( $( $x:expr ),* ) => {
        {
            let mut temp_vec = Vec::new();
            $(
                temp_vec.push($x);
            )*
            temp_vec
        }
    };
}

#[macro_export]表示将定义的宏将导出crate,这样不仅在定义了这个macro的crate的内部可以使用该宏,导入该crate的其它crate亦可使用这个宏。
然后看这个声明宏的定义,非常像rust语中的匹配表达式(match expression)。$(x:expr)$()* 语法表,表示展开为0条或者多条表达式,其他的都比较好理解。
示匹配一个表达式并把匹配到的表达式存在变量$x里。 $(x:expr)被$(),* 包裹。这里有点像正则式的描述,它表示匹配0个或者多个被逗号,分隔的表达式。 =>后面的部分就是描述怎么展开宏了,除了也用到类似正则式的$()* 语法,表示展开为0条或者多条表达式,其他的都比较好理解。
另外,这个宏的定义只使用了一条规则,实际上可以像匹配表达式一样定义多个规则。

Procedure Macros

过程宏可以为一个类自动生成特性trait(类似c++中的纯虚函数,java/c#中的interface)的实现;还能实现类似python中的decoration概念,如下代码所示:

#[route(GET, "/")]
fn index() {
// ...
}

这就跟python的http框架flask用来定义路由的decoration的写法几乎一样了。
不过,编写procedure macros需要使用两个辅助的crate用来操作AST,它们是sync和quote。挺复杂的,你们还是去看官方方档吧。

hygiene是什么

在读官方的Rust Macro相关的资料时,时不时看到hygiene这个詞。一开始不懂这是个什么玩艺儿。后来,才知道原来是rust的宏机制避免了c/c++简单的宏经常出现的副作用。在Rust的话术里,把这个东东称为Hygiene。

就写到这吧,写文章好累呀,还是写代码轻松有意思一些。