wordcount设计与优化

简介:

原文档见:http://gitlab.alibaba-inc.com/middleware/coding4fun-3rd/blob/master/observer.hany/design.md

  • 淘宝中间件第三期编程比赛,题意概述:读入一个文件,统计其中最常出现的前 10 个单词。

系统设计

  • 按照题意,可设计如下简单拓扑图。

0-简单拓扑图

  • 图中方块表示计算节点箭头表示数据流动
    注意: Counter 和 Selector 之间需要设置一道栅栏 ,所有单词统计完毕后才能开始筛选单词。

优化1:同步 OR 异步

  • Reader 是 IO 集中型操作,其他计算节点都是 CPU 集中型操作。
    如果先读完文件再操作,读文件的这段时间 CPU 就白白空闲着浪费掉了。

  • 简单的优化就是异步读文件。
    增加一个后台 Task 线程,Reader 每读取一小块文件数据(Chunk),
    就交给 Task 线程处理,Reader 继续读下一个 Chunk 的时候,Task 已经跑起来了,
    一个占用 IO,一个占用 CPU,充分利用计算机资源。

1-异步读文件

  • 通过异步读文件,Reader 和 Task 能够并发处理数据,提高性能。

实现细节

  • ChunkedTextReader 实现按 Chunk 分块读文件。
    为了避免 Chunk 边界意外将一个单词拆成两半,
    除最后一个 Chunk 外,每个 Chunk 都将末尾的最后一个单词切开,
    拼接到下一个 Chunk 的前面,让下一个 Chunk 处理。
  • Reader 和 Task 之间通过 BlockingQueue 传输数据,
    这是一个线程安全的 "生产者-消费者" 队列。
  • 经测试,Chunk 分块太小队列操作过于频繁,性能下降。
    分块太大读文件阻塞太久,达不到异步读的目的,
    因此默认限制 Chunk 最小 1MB,最大 8MB。

优化2:并发 OR 并发

  • 读文件的速度比处理文件的速度快的多,一个线程 CPU 跑到 100% 也是远远处理不过来。
    测试机有 16 个核,可创建多个并发的 Task 线程,将每个核都利用起来。
    由于 Task 是高度 CPU 密集型操作,默认取 Task 线程数等于 CPU 核数。

2-并发处理

  • 栅栏控制所有数据处理完成才能开始按词频选择单词。

实现细节

  • ConcurrentBlockingQueueExecutor 管理所有 Task 线程,
    executor 在每个线程上等待线程结束,实现栅栏同步。
  • ConcurrentBlockingQueueTask 实现 Task 线程处理流程。
  • Reader 读完文件后在 executor 上设置 done 标识位,
    Task 发现 queue 为空且 executor 设置了 done 标志位,
    则说明文件已经读完并处理完,task 结束。
  • ConcurrentTrieNode 实现了线程安全的 Trie 树。

语言细节

  • 在 Java 实现中,
    ConcurrentBlockingQueueTask 
    ConcurrentBlockingQueueExecutor 互相依赖,
    但 C++ 不能处理互相依赖,
    所以将 task 对 executor 的依赖剥离到
    ConcurrentBlockingQueueExecutorSupport 中,
    避免互相依赖的问题。
    C++程序员通常使用前置声明、分离实现等办法解决互相依赖问题。
  • 程序先用 Java 设计开发完成,再逐个类翻译成 C++。
    编码尽量遵守 Java 约定,
    每个类放到独立的文件,方法实现直接写在头文件的类声明中,".cpp" 文件基本都是空的。
    排除 ".cpp" 文件,文件数量就少一半了,嘿嘿~~
    简单场景还能用 C++ 模拟一下Java,复杂场景就只能用 Java 了。

优化3:双保险模式避免加锁

  • DANGEROUS双保险模式已经被证明是不可靠的,禁止在生产代码中使用。
  • UPDATE@齐楠 @宏江 指出, jdk 1.5 之后加上 volatile 关键字双保险模式是可用的。早期版本不行。
ConcurrentTrieNode* getChild(char c) {
    int const index = c - 'a';
    if (children[index] == NULL) {
        synchronized: {
            Locker locker(childrenLock);
            if (children[index] == NULL) {
                children[index] = (ConcurrentTrieNode*) calloc(1, sizeof(ConcurrentTrieNode));
            }
        }
    }
    return children[index];
}

语言细节

  • ConcurrentTrieNode 是一个简单 struct, 不包含虚函数和复杂对象字段,
    其构造函数只是简单地将所有字段(包括Lock)初始化为 0。
    使用 calloc(1, sizeof(ConcurrentTrieNode)) 直接分配一块 0 初始化的内存,
    calloc 返回内存地址时,已经得到一个合法初始化的 ConcurrentTrieNode 对象,
    而不必调用构造函数。

优化4: 原子操作避免加锁

  • 并发统计 count 时,将 count 字段声明为 volatile(),
/**
 * Word 出现的次数.
 */
volatile int count;
  • 使用原子操作实现线程安全并避免加锁(),提高性能。
// atomic_inc
__asm__ __volatile__(
        "lock ; " "incl %0"
        :"=m" (node->count)
        :"m" (node->count));

优化5:统计单词结束后再过滤排除单词

  • 程序要求排除一些单词,在统计前排除,每个分词都要判断一次。
    统计结束再排除,相同单词已经合并,减少判断,性能更高。

总结

  • 优化过程中曾想过各种方案,
    比如并发 merge sort 排序再处理,每线程一个 Map 最后再合并等,
    结果发现使用 ConcurrentHashMap 不但编程复杂度明显简单,性能还更加理想。
    再一次证明, 最简单的方案往往就是最好的方案 
    不仅从开发维护的角度来看,有时从性能角度来看也是这样。
    Java 的 ConcurrentHashMap 性能相当赞,并发环境首选啊。

  • 程序开始是用 Java ConcurrentHashMap 实现的。
    为了提升性能翻译成 C++,过程可谓大费周折,相当痛苦,我会告诉你我大半夜还在调 segmental fault 吗?
    C++ 没有 ConcurrentHashMap,实现 ConcurrentTrie 相对简单,所以选择了 Trie。
    很多同学采用 Java 实现性能也非常好,相当赞!

相关文章
|
Kubernetes Cloud Native 应用服务中间件
【云原生】使用k8s创建nginx服务—通过yaml文件svc类型暴露
【云原生】使用k8s创建nginx服务—通过yaml文件svc类型暴露
558 0
|
并行计算 TensorFlow 调度
推荐场景GPU优化的探索与实践:CUDA Graph与多流并行的比较与分析
RTP 系统(即 Rank Service),是一个面向搜索和推荐的 ranking 需求,支持多种模型的在线 inference 服务,是阿里智能引擎团队沉淀多年的技术产品。今年,团队在推荐场景的GPU性能优化上又做了新尝试——在RTP上集成了Multi Stream,改变了TensorFlow的单流机制,让多流的执行并行,作为增加GPU并行度的另一种选择。本文详细介绍与比较了CUDA Graph与多流并行这两个方案,以及团队的实践成果与心得。
|
机器学习/深度学习 自然语言处理
自然语言处理Transformer模型最详细讲解(图解版)
自然语言处理Transformer模型最详细讲解(图解版)
10213 1
自然语言处理Transformer模型最详细讲解(图解版)
|
8月前
|
缓存 NoSQL 调度
Tair:基于KV缓存的推理加速服务
Tair 是阿里云基于KV缓存的推理加速服务,旨在优化大模型推理过程中的性能与资源利用。内容分为三部分:首先介绍大模型推理服务面临的挑战,如性能优化和服务化需求;其次讲解Nvidia TensorRT-LLM推理加速库的特点,包括高性能、功能丰富和开箱即用;最后重点介绍基于KVCache优化的推理加速服务,通过Tair的KV缓存技术提升推理效率,特别是在处理长上下文和多人对话场景中表现出色。整体方案结合了硬件加速与软件优化,实现了显著的性能提升和成本降低。
833 3
|
机器学习/深度学习 自然语言处理 数据挖掘
RouteLLM:高效LLM路由框架,可以动态选择优化成本与响应质量的平衡
新框架提出智能路由选择在强弱语言模型间,利用用户偏好的学习来预测强模型胜率,基于成本阈值做决策。在大规模LLMs部署中,该方法显著降低成本而不牺牲响应质量。研究显示,经过矩阵分解和BERT等技术训练的路由器在多个基准上提升性能,降低强模型调用,提高APGR。通过数据增强,如MMLU和GPT-4评审数据,路由器在GSM8K、MMLU等测试中展现出色的性能提升和成本效率。未来将测试更多模型组合以验证迁移学习能力。该框架为LLMs部署提供了成本-性能优化的解决方案。
607 2
|
11月前
|
机器学习/深度学习 人工智能 自然语言处理
前端大模型入门(三):编码(Tokenizer)和嵌入(Embedding)解析 - llm的输入
本文介绍了大规模语言模型(LLM)中的两个核心概念:Tokenizer和Embedding。Tokenizer将文本转换为模型可处理的数字ID,而Embedding则将这些ID转化为能捕捉语义关系的稠密向量。文章通过具体示例和代码展示了两者的实现方法,帮助读者理解其基本原理和应用场景。
2926 1
|
机器学习/深度学习 人工智能 分布式计算
阿里云人工智能平台PAI论文入选OSDI '24
阿里云人工智能平台PAI的论文《Llumnix: Dynamic Scheduling for Large Language Model Serving》被OSDI '24录用。论文通过对大语言模型(LLM)推理请求的动态调度,大幅提升了推理服务质量和性价比。
|
机器学习/深度学习 算法 Python
CatBoost中级教程:模型解释与调试
CatBoost中级教程:模型解释与调试【2月更文挑战第10天】
805 0
|
并行计算 PyTorch 算法框架/工具
基于mps的pytorch 多实例并行推理
基于mps的pytorch 多实例并行推理
682 1
|
机器学习/深度学习 分布式计算 调度
机器学习分布式框架Ray
Ray是UC Berkeley RISELab推出的一个高性能分布式执行框架,它比Spark更具计算优势,部署简单,支持机器学习和深度学习的分布式训练。Ray包括节点(head和worker)、本地调度器、object store、全局调度器(GCS),用于处理各种分布式计算任务。它支持超参数调优(Ray Tune)、梯度下降(Ray SGD)、推理服务(Ray SERVE)等。安装简单,可通过`pip install ray`。使用时,利用`@ray.remote`装饰器将函数转换为分布式任务,通过`.remote`提交并用`ray.get`获取结果。5月更文挑战第15天
2039 7