数字与数组 对js运行效率的影响

[981377660LMT]

const INF = 2**31  // 8500ms
// const INF = 2**31 - 1 // 3500ms

class StockSpanner {
  private readonly _Q: RightMostLeftMostQuerySegmentTree
  private _ptr = 0

  constructor() {
    this._Q = new RightMostLeftMostQuerySegmentTree(Array(1e5 + 10).fill(0))
  }

  next(price: number): number {
    const pos = this._ptr++
    this._Q.set(pos, price)
    const higherPos = this._Q.leftNearestHigher(pos)
    return higherPos === -1 ? pos + 1 : pos - higherPos
  }
}

type E = { min: number; max: number }
type Id = number

class RightMostLeftMostQuerySegmentTree {
  private readonly _n: number
  private readonly _rangeAddRangeMinMax: SegmentTreeRangeUpdateRangeQuery<E, Id>

  constructor(arr: ArrayLike<number>) {
    this._n = arr.length
    const leaves: E[] = Array(this._n)
    for (let i = 0; i < this._n; i++) leaves[i] = { min: arr[i], max: arr[i] }
    this._rangeAddRangeMinMax = new SegmentTreeRangeUpdateRangeQuery<E, Id>(leaves, {
      e: () => ({ min: INF, max: -INF }),
      id: () => 0,
      op: (a, b) => ({ min: a.min > b.min ? a.min : b.min, max: a.max > b.max ? a.max : b.max }),
      mapping: (f, x) => (f === 0 ? x : { min: f + x.min, max: f + x.max }),
      composition: (f, g) => f + g
    })
  }

  set(index: number, value: number): void {
    if (index < 0 || index >= this._n) return
    this._rangeAddRangeMinMax.set(index, { min: value, max: value })
  }

  /**
   * 查询`index`左侧最近的下标`j`，使得 `nums[j] > nums[index]`.
   * 如果不存在，返回`-1`.
   */
  leftNearestHigher(index: number): number {
    const cur = this._rangeAddRangeMinMax.get(index).max
    const cand = this._rangeAddRangeMinMax.minLeft(index, e => e.max <= cur) - 1
    return cand === -1 ? -1 : cand
  }
}

class SegmentTreeRangeUpdateRangeQuery<E = number, Id = number> {
  private readonly _n: number
  private readonly _size: number
  private readonly _height: number
  private readonly _data: E[]
  private readonly _lazy: Id[]
  private readonly _e: () => E
  private readonly _id: () => Id
  private readonly _op: (a: E, b: E) => E
  private readonly _mapping: (id: Id, data: E) => E
  private readonly _composition: (id1: Id, id2: Id) => Id

  /**
   * 区间修改区间查询的懒标记线段树.维护幺半群.
   * @param nOrLeaves 大小或叶子节点的值.
   * @param operations 线段树的操作.
   */
  constructor(
    nOrLeaves: number | ArrayLike<E>,
    operations: {
      /**
       * 线段树维护的值的幺元.
       */
      e: () => E

      /**
       * 更新操作/懒标记的幺元.
       */
      id: () => Id

      /**
       * 合并左右区间的值.
       */
      op: (e1: E, e2: E) => E

      /**
       * 父结点的懒标记更新子结点的值.
       */
      mapping: (lazy: Id, data: E) => E

      /**
       * 父结点的懒标记更新子结点的懒标记(合并).
       */
      composition: (f: Id, g: Id) => Id

      /**
       * 判断两个懒标记是否相等.比较方式默认为`===`.
       */
      equalsId?: (id1: Id, id2: Id) => boolean
    } & ThisType<void>
  ) {
    const n = typeof nOrLeaves === 'number' ? nOrLeaves : nOrLeaves.length
    const { e, id, op, mapping, composition } = operations

    let height = 32 - Math.clz32(n - 1)
    let size = 1 << height

    const data = Array(size << 1)
    for (let i = 0; i < data.length; i++) data[i] = e()
    const lazy = Array(size)
    for (let i = 0; i < lazy.length; i++) lazy[i] = 0
    this._n = n
    this._size = size
    this._height = height
    this._data = data
    this._lazy = lazy
    this._e = e
    this._id = id
    this._op = op
    this._mapping = mapping
    this._composition = composition

    if (typeof nOrLeaves !== 'number') this.build(nOrLeaves)
  }

  set(index: number, value: E): void {
    if (index < 0 || index >= this._n) return
    index += this._size
    for (let i = this._height; i > 0; i--) this._pushDown(index >> i)
    this._data[index] = value
    for (let i = 1; i <= this._height; i++) this._pushUp(index >> i)
  }

  get(index: number): E {
    if (index < 0 || index >= this._n) return this._e()
    index += this._size
    for (let i = this._height; i > 0; i--) this._pushDown(index >> i)
    return this._data[index]
  }

  /**
   * 树上二分查询最小的`start`使得`[start,end)`内的值满足`predicate`
   * @alias findLast
   */
  minLeft(end: number, predicate: (value: E) => boolean): number {
    if (end > this._n) end = this._n
    if (end <= 0) return 0
    end += this._size
    for (let i = this._height; i > 0; i--) this._pushDown((end - 1) >> i)
    let res = this._e()
    while (true) {
      end--
      while (end > 1 && end & 1) end >>= 1
      if (!predicate(this._op(this._data[end], res))) {
        while (end < this._size) {
          this._pushDown(end)
          end = (end << 1) | 1
          if (predicate(this._op(this._data[end], res))) {
            res = this._op(this._data[end], res)
            end--
          }
        }
        return end + 1 - this._size
      }
      res = this._op(this._data[end], res)
      if ((end & -end) === end) break
    }
    return 0
  }

  build(leaves: ArrayLike<E>): void {
    if (leaves.length !== this._n) throw new RangeError(`length must be equal to ${this._n}`)
    for (let i = 0; i < this._n; i++) this._data[this._size + i] = leaves[i]
    for (let i = this._size - 1; i > 0; i--) this._pushUp(i)
  }

  private _pushUp(index: number): void {
    this._data[index] = this._op(this._data[index << 1], this._data[(index << 1) | 1])
  }

  private _pushDown(index: number): void {
    const lazy = this._lazy[index]
    if (lazy === 0) return
    this._propagate(index << 1, lazy)
    this._propagate((index << 1) | 1, lazy)
    this._lazy[index] = 0 as Id
  }

  private _propagate(index: number, lazy: Id): void {
    this._data[index] = this._mapping(lazy, this._data[index])
    if (index < this._size) this._lazy[index] = this._composition(lazy, this._lazy[index])
  }
}

[981377660LMT]

js里number的范围对执行效率影响也很大。

同一份代码，令 INF = 2**31 需要 8500ms， 令 INF = 2**31 - 1 需要 3500ms 正好是int32

[981377660LMT]

// !1.数字大小的影响
// INF = 2**31 需要 8500ms，
// INF = 2**31 - 1 需要 3500ms
// (参考v8优化方案)
// !2.数组与对象的性能差异(对象快于数组)
// type E = [min: number, max: number]  // 6500ms, 138MB
// type E = { min: number; max: number } // 3500ms, 108MB
// !3.number与对象的性能差异
// type E = { min: number; max: number } // 3500ms, 108MB
// type E = number // 800ms, 82MB
// !4.将普通数组number[]换成Float64Array
// number[] // 800ms, 82MB
// Float64Array // 550ms, 70MB
// !类型数组的数字不受范围影响(例如INF的取值影响效率)

[981377660LMT]

得出优化结论:

1. 尽量使用number而不是对象，尽量使用对象存pair而不是数组.
2. 如果数组只存整数,不超过int32使用Uint32Array，超过uint32使用Float64Array.
3. 如果数据范围在int32内，尽量使用2e9作为INF，否则使用 2e15 或者 Infinity。

[981377660LMT]

https://zhuanlan.zhihu.com/p/84453627 同样是占32个坑，凭啥你float就比int的范围更大？

https://blog.csdn.net/opk8848/article/details/103240945 int32 float 在c++中同样都是32位，但是存储结构完全不同。 int32 先不说 float是这样表达的。关键词IEEE 754 float在内存中 分三部分 s+e+m s 1位 0代表正数 1 负数 e 8位 代表 移多少位 m 23位 是小数的具体数字 （24位最高位总为1，所以丢弃不存） 对应float64: s 1 e 11 m 52

[981377660LMT]

v8 优化相关

https://lyn-ho.github.io/posts/4d26265b/ https://zhuanlan.zhihu.com/p/591353951

• 不要随便地使用 delete 或者 增加一个属性，因为这样会导致 隐藏类失效而 重新 构建一个新的隐藏类
• 使用字面量初始化对象时，要保证属性的顺序是一致的，
• 例如 var a = {x: 1, y: 2}; b = {y: 1, x : 2} 这样会导致 创建两个 隐藏类
• 慎用全局变量，因为会顺着作用域链查找变量，查找的层级越高，速度就越慢
• 缓存全局变量，例如： 在 一个函数内部，如果需要调用 document.createElement 等函数的时候，先将var doc = document 缓存起来，这样 doc 就不是全局变量了，而是 在 同一个 作用域中的值
• 使用 字面量的 方法创建一个 数组或者对象，而不是使用 new Object 或者 new Array

---

https://panzhongxian.cn/cn/2021/04/02-inside-the-v8-engine-5-tips-on-how-to-write-optimized-code/

• 内联 (Inlining)
• 隐藏类 (Hidden class) 由于使用字典来查找对象属性在内存中的位置非常低效，因此 V8 使用了一种技巧：隐藏类。隐藏类的工作方式类似于 Java 之类的语言中使用的固定对象布局（类），不同之处在于隐藏类是在运行时创建的。
• 编写优化 JavaScript 的 5 个技巧

1. 对象属性的顺序：始终以相同的顺序实例化对象属性，以便可以共享隐藏的类以及随后优化的代码。
2. 动态属性：实例化后向对象添加属性将强制更改隐藏类，已经为上一个隐藏类优化过的方法都会因此而变慢。替代措施是在构造函数中分配对象的所有属性。
3. 方法：由于内联缓存 (inline caching) 的原因，重复执行相同方法将比仅执行一次许多不同方法的代码运行更快。
4. 数组：避免键不是递增数字的稀疏数组。里面没有所有元素的稀疏数组是一个“哈希表”。访问这样数组中的元素耗费更大。另外，避免预先分配大数组，在使用中逐渐增长更好。最后，不要删除数组中的元素，它使键更稀疏。
5. 标记值 (tagged values)：V8 使用 32 位表示对象和数字。它使用 32 bit 中的一个 bit 来标记变量是对象（flag = 1），还是的整数（flag = 0），这个整数被称为”小整数(SMI, SMall Integer)“，因为它只有 31 bit。如果数值大于 31 位，则 V8 会将数字装箱 (box)，将其变成 double 并创建一个新对象以将数字放入其中。尽可能使用 31 bit 带符号的数字，以避免对 JS 对象进行昂贵的装箱操作。 注意：smi：32位中使用的是i30，在64位系统上，V8则会使用i31

---

https://zhuanlan.zhihu.com/p/29638866?from_voters_page=true JavaScript 在 V8 中的元素种类及性能优化

• 三种不同的元素，具有以下基本类型： 小整数，又称 Smi。(可以理解为int32) 双精度浮点数，浮点数和不能表示为 Smi 的整数。 常规元素，不能表示为 Smi 或双精度的值。

  const array = [1, 2, 3];
  // 元素类型: PACKED_SMI_ELEMENTS
  array.push(4.56);
  // 元素类型: PACKED_DOUBLE_ELEMENTS
  array.push('x');
  // 元素类型: PACKED_ELEMENTS

  

为了获得最佳性能，请避免不必要的不具体类型 - 坚持使用符合您情况的最具体的类型。

---

JavaScript高性能的秘密———探索V8引擎 https://zhuanlan.zhihu.com/p/368320375

js中的Number类型看起来十分简单，不需要关心什么Int、Float、32、64，统统都是Number。看起来js引擎内部只要选择一个最大范围的类型（比如Float64）就可以表示js中的所有Number，但在v8内部可没这么简单。

Smi vs HeapNumber

在V8内部，会把Number类型分成两大类型，一种是Smi(small integer的缩写)和 Heap Number。 Smi，小整数，顾名思义用来表示一个小范围内的整数类型： -(2^30) ~ 2^30 - 1 范围内的整数，我们知道Int32类型的范围是 -(2^31) ~ 2^31 - 1, 为什么Smi类型会比Int32小呢，这是因为在V8中，Sim类型的值是根据它的地址直接得出的，为了区分Smi类型和普通的指针，Smi类型都存储在最低位为0的地址中，所以Smi的范围实际上是Int31类型的范围。

V8中对于32位系统和64位系统中的指针也有不同处理，简单来说V8把内存分为一个个4GB大小的区块，因为4GB正好是2 ^ 32byte, 于是可以不用关心一个地址的前32位，根据末位是否为0来判断一个地址是Smi还是普通指针，如果是Smi则读取它的值，如果是普通指针则加上当前区块的offset。这样做的好处是可以在64位的系统上使用32位的空间来储存一个地址，避免了很多空间的浪费，也正好符合许多浏览器中JS最高使用内存4GB的限制。

HeapNumber 与Sim对应，HeapNumber则用来表示无法用Smi表示其他Number类型，包括有小数点的数值, 超过Smi范围的整数, Number.NaN, Infinity等任何不能用Smi表示的Number类型。HeapNumber在V8内部是一个对象，储存在堆内存上，它的名字也体现出了这一点。HeapNumber类型的值是不可变，如果要修改，会创建一个新的HeapNumber并赋值。

JavaScript中把数据类型分为基本类型和引用类型2种，实际在基本类型的背后，有很多是用像HeapNumber这样的对象来表示的，只不过在js使用者看来并不能感受到这样的隐藏逻辑。

一切对象的原型-Object类型 Object是js中十分常用的数据类型。由于JS采用原型继承，一切对象都最终继承Object。在JS中Object可以简单地声明、添加和删除属性，而且value可以是任意类型，看起来表现的很像hash table。但是在V8引擎内部，并不是简单的用hash table来表示Object的，为了兼顾内存占用和执行效率，V8为Object类型做了很多复杂的工作。

Object中的属性 首先，通常情况下，虽然Object表现得像一个字典数据结构，但是在V8中Object中的属性值是存储在一个独立的数组中的。而这样存储的属性值是无法直接通过key直接访问的，因此还需要一些其他的元数据，V8中使用了一种叫做隐藏类型的机制来储存这些元数据，每个js对象都有一个对应的隐藏类型(HiddenClass)。隐藏类型存储的信息包括：对象的形态、从属性的key到属性值在数组中位置的映射。

[981377660LMT]

好的方法是当成golang写

[981377660LMT]

https://fex.meishakeji.com/2020/08/10/V8%20%E7%9A%84%E6%80%A7%E8%83%BD%E4%BC%98%E5%8C%96%E7%AD%96%E7%95%A5/ V8 的性能优化策略

[981377660LMT]

获取o.x的流程为：查找对象 o 的隐藏类，通过隐藏类查找属性x的偏移量，然后通过偏移量（相对对象o的）获取属性值。这里经过三个步骤，在for循环中反复执行了loadX函数去获取 o.x，是否有办法去简化获取过程？这个时候就该内联缓存（Inline Cache）登场了。

V8 在执行函数的过程会观察一些调用点上的关键“中间数据”，然后将这些数据缓存起来，下次再执行该函数的时候，V8就可以直接利用这些“中间数据”，以此节约再次获取这些数据的过程。

[981377660LMT]

https://cloud.tencent.com/developer/article/1083755

这也解释了为什么js的位运算只支持in32

[981377660LMT]

https://blog.csdn.net/dongcehao/article/details/106319280