Hasty Briefsbeta

全部标签

#optimization

共 158 篇

双语

Show HN: Tacopy – Tail Call Optimization for Python
6 months ago
- Tacopy是一个Python库，通过将尾递归函数转换为迭代循环来优化其性能
- 通过处理超出Python默认限制的深度递归，有效防止栈溢出错误
- 提供性能提升，使函数执行速度比标准递归快1.41至2.88倍
- 包含验证机制，确保函数在转换前是严格尾递归的
- 保留函数元数据（如文档字符串和类型提示）且无运行时开销
- 支持pip或uv一键安装，使用只需用@tacopy装饰目标函数
- 演示案例涵盖阶乘、斐波那契数列、最大公约数和求和计算
- 当前限制包括仅支持模块级函数、不支持异步、要求Python 3.10+版本
- 配备完整测试套件和基准测试，显示显著的加速效果
- 采用GNU GPL v3.0开源协议，欢迎社区贡献
My favourite small hash table
5 months ago
- 文章讨论了一种特定的哈希表设计，采用罗宾汉开放寻址法结合线性探测和二次幂表大小。
- 键为32位整数，值同样为32位整数，使得键值对可以存储为64位整数。
- 哈希表结构包含槽位（64位整数数组）、掩码（表大小减一）以及非空槽位计数。
- 查找过程涉及检查键的自然位置，若发生冲突则线性探测，并通过评分函数决定终止条件。
- 插入操作会检查现有键，必要时通过重新插入键处理冲突，并在75%负载因子时触发表扩容。
- 键删除通过左移槽位直到遇到空槽或评分为零的槽位实现，避免了墓碑标记的需求。
- 迭代过程直接遍历数组并过滤空槽位。
- 该设计可通过可逆哈希函数扩展至非随机分布键，或通过分离存储支持更大的键值对。
- 文章指出其局限性，例如不适用于无锁并发场景或需要特定硬件指令的情况。
Super-Flat ASTs
5 months ago
- 介绍如何优化一种简单编程语言的解析器。
- 当前实现采用递归下降解析器生成AST，内存占用较高。
- 基准测试主要关注吞吐量（每秒代码行数）和最大内存使用量。
- 引入字符串驻留技术，通过重用字符串和标识符来降低内存占用。
- 采用指针压缩和平坦化AST表示以进一步优化内存和性能。
- 使用碰撞分配法分摊内存分配成本，提高速度并减少内存占用。
- 提出超平坦AST表示以实现更高效率，包含详细实现方案。
- 结果显示每个优化步骤都显著提升了速度和内存使用效率。
Fast Median Filter over arbitrary datatypes
5 months ago
- 中值滤波器是计算机视觉中常见的滤波器，存在多种优化版本。
- V1：基础版中值滤波器实现，通过排序计算中值。
- V2：使用快速选择算法实现线性时间复杂度中值查找，提升性能。
- V3：多线程并行处理实现，达到16倍加速。
- V4：采用位集表示的序数变换中值计算，实现420倍加速。
- 讨论了通用数据类型的局限性及针对uint8类型的潜在优化方案。
Building small Docker images faster
5 months ago
- 在工作中使用Go语言构建更小更快的Docker镜像来部署新服务
- 最初使用Nix构建最小化OCI镜像，后因团队偏好切换至Docker方案
- 演示如何为Goose迁移工具构建仅15.9MB的超小Docker镜像
- 通过管理构建上下文、使用缓存挂载和绑定挂载来优化Docker构建效率
- 采用多阶段构建的Dockerfile结构以最小化最终镜像体积
- 提升构建速度和缩减镜像尺寸的技巧：包括.dockerignore文件和小型基础镜像的使用
- 介绍Docker Compose的watch模式实现文件变更自动重建功能
Faster Double-to-String Conversion
5 months ago
- 新开发了一种二进制到十进制的浮点数转换方法，其性能超越了现有算法如Dragonbox、Schubfach和std::to_chars。
- 性能提升包括：在macOS上比Dragonbox快约68%，比sprintf快约59倍。
- 关键优化措施包括：减少整数乘法运算、更快的对数近似计算以及无分支处理不规则舍入区间。
- 该方法将候选数字数量从2-4个减少到1-3个，从而简化了转换流程。
- 在有效数字和指数输出方面的改进包括：使用查找表获取十进制数字，以及无分支去除末尾零。
- 该算法计划集成到{fmt}库中，并可能为Thrift等应用的JSON序列化带来性能提升。
- 当前局限性在于仅支持科学计数法格式，未来计划增加定点数格式支持。
I've been writing ring buffers wrong all these years (2016)
5 months ago
- 实现单元素环形缓冲区具有挑战性，传统实现方式会浪费存储空间。
- 两种常见环形缓冲区实现：双索引（读/写）数组 vs 单索引加长度数组。
- 传统双索引实现需浪费一个数组元素来区分空/满状态。
- 单索引加长度方案虽能利用全部容量，但使并发访问复杂化。
- 创新方案：使用两个无掩码的无限增长索引，仅在数组寻址时进行掩码操作。
- 无掩码索引优势：代码更简洁、零空间浪费，但需满足容量为2的幂且依赖无符号整数回绕特性。
- 该技术早在2004年就有记载，却仍未得到广泛应用。
- 可能原因：传统思维定式、对整数溢出的顾虑，或非2的幂容量需求。
- 通过模运算可支持非2的幂容量，但会牺牲性能。
Huge binaries: I thunk therefore I am
5 months ago
- 文章讨论了x86_64链接的'声音屏障'问题，特别是32位相对CALL指令可能导致重定位溢出的情况。
- 使用-mcmodel=large可以解决问题，但会导致'指令膨胀'和潜在的性能损失。
- 动态库是避免静态链接问题的常见解决方案，但会引入性能开销和部署复杂性。
- 链接时优化(LTO)提供高级优化功能，但需要大量内存且会拖慢构建速度，目前正研究ThinLTO和配置文件引导优化。
- 链接器跳板(thunks/trampolines)被提议作为解决方案，可在大二进制文件中保持快速的小代码模型，LLVM在AArch64等架构中已有先例。
- 文章探讨了为x86_64实现跳板以突破2GiB限制的可能性，建议修改GOT和PLT访问方式。
- 作者邀请合作者共同探索这些方案，强调需要在二进制大小和性能之间进行权衡取舍。
Pokémon Team Optimization
5 months ago
- 作者回忆童年对宝可梦的热爱，包括玩游戏、看动画和收集周边商品。
- 成年后作者重新接触宝可梦游戏，但发现自己采用数值最小化/最大化的组队策略，而非童年时只用一只强力宝可梦的玩法。
- 作者将优化宝可梦队伍构建问题建模为混合整数规划(MIP)，核心目标是最大化基础数值并确保属性抗性。
- 关键约束条件包括选择1-6只宝可梦、确保覆盖所有属性抗性、以及避免重复选择相同宝可梦。
- 文章先解释线性规划(LP)和单纯形算法，再讨论用分支定界法处理整数约束。
- 针对属性抗性的非线性约束，通过辅助变量强制满足逻辑条件来实现。
- 作者使用Python的PuLP库实现该方案，并采用Kaggle上的宝可梦数值数据集。
- 优化结果显示最佳队伍包含传说宝可梦和准传说宝可梦，兼具高基础数值和强力属性抗性。
- 当排除传说级宝可梦后，普通宝可梦组成的队伍在基础数值与抗性之间展现出明显权衡关系。
- 该项目展示了运筹学方法在游戏策略中的应用，并具有进一步定制化的潜力。
Why German Strings Are Everywhere?
4 months ago
- 字符串不仅仅是字符序列，其复杂性导致不同编程语言存在多样化实现方式。
- German Strings由Umbra（CedarDB前身）开发，专为数据处理优化，被DuckDB和Apache Arrow等系统采用。
- C语言字符串简单但笨拙，需要手动管理内存且缺乏内置安全特性。
- C++字符串通过尺寸追踪、缓冲区容量和短字符串优化(SSO)等特性改进了C语言的不足。
- German Strings针对常见场景优化：短字符串、不可变性和前缀比较。
- 短字符串（≤12字符）采用就地存储，避免指针解引用从而提升访问速度。
- 长字符串（>12字符）存储4字符前缀以加速比较，避免不必要的解引用操作。
- German Strings使用128位结构体，节省空间并通过寄存器实现高效函数调用。
- 存储类别（持久化、临时性、瞬时性）管理字符串生命周期，优化内存使用和性能。
- 瞬时字符串指向外部托管内存，降低临时数据访问的开销。
- German Strings虽具性能优势，但需谨慎考虑字符串生命周期和不可变性约束。
I got paid minimum wage to solve an impossible problem
4 months ago
- 这位计算机科学专业的学生作者尝试将超市扫地任务优化为网格图问题，并运用模拟退火算法寻找最短路径。
- 最初的优化仅聚焦于最小化行进距离，结果产生了充满急转弯的不实用路径，完全不适合人类操作。
- 作者意识到错误在于优化了错误指标（距离），于是改进算法加入'转向惩罚系数'，最终生成更平滑实用的清扫路线。
- 该实验揭示了一个普遍问题：算法常优化那些易量化指标（如参与度或利润），却与真实需求（如幸福感或可持续性）背道而驰。
- 核心启示：若解决的是错误问题，技术正确性毫无意义。真正的挑战在于最初如何定义优化目标。
Recent Optimizations in Python's Reference Counting
4 months ago
- Python引用计数的最新优化包括新增了一个名为LOAD_FAST_BORROW的字节码指令。
- LOAD_FAST_BORROW在加载局部变量时避免增加引用计数，从而提升热点循环的性能。
- 该优化适用于值在基本代码块内使用、进行简单操作且源值保持不变的情况。
- Python 3.15引入了LOAD_FAST_BORROW_LOAD_FAST_BORROW指令，可通过单个操作码加载两个变量且不增加引用计数。
- CPython使用类似Rust借用概念的控制流图进行生命周期分析，以确保优化安全性。
- 当前正在努力消除JIT编译代码中的冗余引用计数，不过JIT优化目前默认处于禁用状态。
Pigeon's Device (2009)
4 months ago
- 鸽式装置（Pigeon's device）是C语言中的一种循环优化技术，类似于达夫设备（Duff's device）但独立起源。
- 最初用于比较不同排序模式下日期/时间记录的函数：FORWARD（正向）、REVERSE（反向）和REVDFWDT（日期反向时间正向）。
- 该技术通过将if语句与switch语句交织，根据模式和条件控制流程。
- 由于函数通过库排序例程调用且无第三参数，采用『骇客手法』设置和读取比较模式。
- 函数通过三种方式处理不同排序模式：正向比较日期、反向比较日期，或混合模式（同一天内日期反向但时间正向比较）。
- 默认分支作为错误捕获器，用于处理无效的模式值。
LLVM: The Bad Parts
4 months ago
- LLVM面临评审能力不足的挑战，导致PR审核缓慢且可能合并不良变更
- 该项目C++ API和IR变更频繁，需在创新与稳定性成本间取得平衡
- 由于LLVM的庞大体积和C++编译开销，构建耗时显著，现有部分缓解策略
- 持续集成稳定性问题持续存在，包括不稳定测试和构建节点故障，掩盖了真实失败信号
- 端到端测试覆盖不足，特别是可执行测试和完整操作流程的验证
- 后端分歧问题突出，修复方案常针对特定目标而非通用解决
- 编译时间仍是痛点，尽管近期有改进，-O0级别优化尤其明显
- 性能追踪体系不完善，缺乏官方运行时性能监控基础设施
- IR设计存在缺陷，包括未定义值问题、逻辑不严谨及规范不完整
- 约束编码机制分散，多种实现方式各有取舍
- 非严格IEEE 754标准的浮点语义处理存在问题
- 新Pass管理器等部分迁移工作持续多年仍未完全落地
- ABI和调用约定处理混乱，前后端间缺乏清晰契约
- 内置函数和库函数管理复杂，存在多数据源冲突且缺乏定制能力
- 上下文/模块二分法设计导致数据布局访问等摩擦
- LICM优化增加寄存器压力，却缺乏后端下沉机制有效缓解
Challenges in Join Optimization
4 months ago
- StarRocks通过保持数据规范化并实现高速实时连接来优化查询性能。
- 文章从四个维度解析StarRocks基于成本的优化器：连接基础原理、逻辑连接优化、连接顺序重排和分布式连接规划。
- 常见连接类型包括笛卡尔积、全外/左/右连接、反连接、半连接和内连接，各自具有不同的性能特征。
- 连接优化面临多重挑战：多种连接实现策略选择、连接顺序决策、连接效果评估困难以及分布式系统复杂性。
- StarRocks采用哈希连接作为核心算法，并应用谓词下推、谓词提取、等价推导和限制条件下推等优化技术。
- 连接顺序重排策略涵盖穷举法、贪婪算法和动态规划法，以确定最优连接顺序。
- 分布式连接方案包含Shuffle连接、广播连接、桶Shuffle连接、协同定位连接和复制连接，最大限度降低网络开销。
- 全局运行时过滤器通过Min/Max值过滤、IN谓词和布隆过滤器提前剔除无关数据行，有效缩减连接输入规模。
- 来自NAVER、Demandbase和Shopee的案例表明，借助StarRocks高效的连接执行引擎可实现显著的性能提升与成本节约。
SFPark: Interactive map of SF parking regulations
4 months ago
- SFPark是一款交互式地图应用，旨在帮助用户更高效地掌握旧金山停车规定
- 该项目源于避免因停车标识不清或遗漏而导致罚单的实际需求
- 开发者借助Claude AI快速完成应用原型设计和优化，将开发周期从数周缩短至数天
- 应用采用来自data.sfgov.org和services.sfmta.com的公开GeoJSON数据，并进行了预处理以提升效率
- 关键优化包括将坐标量化为32位整数、压缩数据体积、提升渲染性能
- 前端设计轻量化，依赖项极少，同时支持canvas和WebGL渲染以确保流畅体验
- 后端设置每小时自动更新数据的任务，以最小开销保障停车信息实时性
- 该项目印证了AI作为'高级编译器'的潜力，能够快速开发定制化软件解决方案
A Complete Guide to Neural Network Optimizers
4 months ago
- 神经网络训练是一个优化问题，旨在通过寻找最佳权重来最小化损失函数。
- 优化算法帮助在具有低谷、平台和鞍点的复杂损失地形中导航。
- 讨论了七种关键优化器：SGD（随机梯度下降）、Momentum（动量法）、Nesterov Momentum（涅斯捷罗夫动量）、AdaGrad、RMSProp、Adam 和 AdamW。
- SGD简单但可能因固定学习率而产生振荡且收敛缓慢。
- 动量法通过累积梯度减少振荡，在方向一致的路径上加速收敛。
- 涅斯捷罗夫动量通过预判未来梯度方向改进动量法，实现更精准的参数更新。
- AdaGrad根据参数自适应调整学习率，适用于稀疏梯度但存在学习率快速衰减的问题。
- RMSProp采用平方梯度的指数加权平均来稳定学习率。
- Adam结合动量法和RMSProp，提供带偏差校正的自适应学习率和动量。
- AdamW将权重衰减与梯度更新解耦，相比Adam具有更好的泛化性能。
- 优化器选择需考虑数据集规模、梯度稀疏性和计算资源等问题特性。
- Adam和AdamW因鲁棒性广受欢迎，但SGD加动量法在某些任务中仍具竞争力。
Why my Rust benchmarks were wrong, or how to use std:hint:black_box? (2022)
4 months ago
- 这篇博客文章探讨了在Rust基准测试中正确使用`std::hint::black_box`的方法，以防止编译器优化扭曲测试结果。
- 文章解释了`black_box`函数的工作原理：通过强制编译器将值视为易变的，从而避免对被测试代码进行优化。
- 文中提供了错误基准测试的示例，展示编译器如何优化掉被测代码，导致虚假的快速结果。
- 对比了不同实现方式的`black_box`，包括标准库的内置版本和更有效的基于汇编的版本。
- 作者通过`char::to_digit`和`str::parse::<f64>`等实际基准测试案例，演示了缺少`black_box`会导致测量失准的情况。
- 文章最后展示了正确应用`black_box`后的更新基准测试结果，这些数据反映了更准确的性能指标。
- 尽管基准测试存在局限性，但作者认为它仍具价值，并推荐使用性能剖析工具和Compiler Explorer等辅助优化工作。
Show HN: SimpleSVGs – Free Online SVG Optimizer Multiple SVG Files at Once
4 months ago
- 优化SVG文件以减小体积，同时保持质量无损。
- 通过拖放或点击浏览上传SVG文件。
- SVG优化工具快速将矢量图形转换为轻量级、可直接用于生产的资源。
- 在浏览器中即时处理SVG，无需上传至服务器，实现零延迟。
- 简洁的代码结构有助于提升SEO和核心网页指标。
- 批量处理功能支持同时优化多个文件，节省时间。
- SimpleSVGs提供基于浏览器的安全SVG压缩与代码清理方案，确保完全隐私。
Building Your Own Efficient uint128 in C++
3 months ago
- 在C++中使用两个u64位段实现固定宽度uint128以支持高效算术运算
- 利用_addcarry_u64、_subborrow_u64和_mulx_u64等内联函数直接映射x64指令
- 与内置__uint128_t生成的汇编代码对比显示基础操作性能相同
- 专注于无符号运算、固定宽度及现代x64架构，附带MSVC和AArch64平台说明
- 基于\(2^{64}\)进制的乘法策略解析及高位截断优化
- 利用硬件借位标志实现最少分支的比较操作
- 扩展更大整数类型及有符号变体的可能性探讨
- PowerPC平台注意事项、GCC代码生成特性及大整数除法不切实际性的说明
- 提及_BitInt(N)类型及其在超过128位时的性能缺陷

About|Login

#optimization

Show HN: Tacopy – Tail Call Optimization for Python

My favourite small hash table

Super-Flat ASTs

Fast Median Filter over arbitrary datatypes

Building small Docker images faster

Faster Double-to-String Conversion

I've been writing ring buffers wrong all these years (2016)

Huge binaries: I thunk therefore I am

Pokémon Team Optimization

Why German Strings Are Everywhere?

I got paid minimum wage to solve an impossible problem

Recent Optimizations in Python's Reference Counting

Pigeon's Device (2009)

LLVM: The Bad Parts

Challenges in Join Optimization

SFPark: Interactive map of SF parking regulations

A Complete Guide to Neural Network Optimizers

Why my Rust benchmarks were wrong, or how to use std:hint:black_box? (2022)

Show HN: SimpleSVGs – Free Online SVG Optimizer Multiple SVG Files at Once

Building Your Own Efficient uint128 in C++