From owner-svn-src-head@FreeBSD.ORG Wed Jun 4 03:02:50 2014 Return-Path: Delivered-To: svn-src-head@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:1900:2254:206a::19:1]) (using TLSv1 with cipher ADH-AES256-SHA (256/256 bits)) (No client certificate requested) by hub.freebsd.org (Postfix) with ESMTPS id 3CF869C3; Wed, 4 Jun 2014 03:02:50 +0000 (UTC) Received: from svn.freebsd.org (svn.freebsd.org [IPv6:2001:1900:2254:2068::e6a:0]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client did not present a certificate) by mx1.freebsd.org (Postfix) with ESMTPS id 0CA74285E; Wed, 4 Jun 2014 03:02:50 +0000 (UTC) Received: from svn.freebsd.org ([127.0.1.70]) by svn.freebsd.org (8.14.8/8.14.8) with ESMTP id s5432npl094686; Wed, 4 Jun 2014 03:02:49 GMT (envelope-from emaste@svn.freebsd.org) Received: (from emaste@localhost) by svn.freebsd.org (8.14.8/8.14.8/Submit) id s5432n6j094685; Wed, 4 Jun 2014 03:02:49 GMT (envelope-from emaste@svn.freebsd.org) Message-Id: <201406040302.s5432n6j094685@svn.freebsd.org> From: Ed Maste Date: Wed, 4 Jun 2014 03:02:49 +0000 (UTC) To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: svn commit: r267035 - head/tools/tools/vt/fontcvt X-SVN-Group: head MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-BeenThere: svn-src-head@freebsd.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: SVN commit messages for the src tree for head/-current List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 04 Jun 2014 03:02:50 -0000 Author: emaste Date: Wed Jun 4 03:02:49 2014 New Revision: 267035 URL: http://svnweb.freebsd.org/changeset/base/267035 Log: vt fontcvt: Use a hash to speed up glyph deduplication Walking a linked list of all glyphs to look for a duplicate is very slow for large fonts (e.g., for CJK character sets). In my test the runtime for a sample 40000 character font went from just over 80 seconds on average to just over 2 seconds. Sponsored by: The FreeBSD Foundation Modified: head/tools/tools/vt/fontcvt/fontcvt.c Modified: head/tools/tools/vt/fontcvt/fontcvt.c ============================================================================== --- head/tools/tools/vt/fontcvt/fontcvt.c Wed Jun 4 01:08:57 2014 (r267034) +++ head/tools/tools/vt/fontcvt/fontcvt.c Wed Jun 4 03:02:49 2014 (r267035) @@ -30,6 +30,8 @@ #include __FBSDID("$FreeBSD$"); +#include +#include #include #include #include @@ -49,11 +51,14 @@ static unsigned int width = 8, wbytes, h struct glyph { TAILQ_ENTRY(glyph) g_list; + SLIST_ENTRY(glyph) g_hash; uint8_t *g_data; unsigned int g_index; }; +#define FONTCVT_NHASH 4096 TAILQ_HEAD(glyph_list, glyph); +static SLIST_HEAD(, glyph) glyph_hash[FONTCVT_NHASH]; static struct glyph_list glyphs[VFNT_MAPS] = { TAILQ_HEAD_INITIALIZER(glyphs[0]), TAILQ_HEAD_INITIALIZER(glyphs[1]), @@ -147,17 +152,16 @@ static struct glyph * add_glyph(const uint8_t *bytes, unsigned int map_idx, int fallback) { struct glyph *gl; - unsigned int i; + int hash; glyph_total++; glyph_count[map_idx]++; - for (i = 0; i < VFNT_MAPS; i++) { - TAILQ_FOREACH(gl, &glyphs[i], g_list) { - if (memcmp(gl->g_data, bytes, wbytes * height) == 0) { - glyph_dupe++; - return (gl); - } + hash = fnv_32_buf(bytes, wbytes * height, FNV1_32_INIT) % FONTCVT_NHASH; + SLIST_FOREACH(gl, &glyph_hash[hash], g_hash) { + if (memcmp(gl->g_data, bytes, wbytes * height) == 0) { + glyph_dupe++; + return (gl); } } @@ -168,6 +172,7 @@ add_glyph(const uint8_t *bytes, unsigned TAILQ_INSERT_HEAD(&glyphs[map_idx], gl, g_list); else TAILQ_INSERT_TAIL(&glyphs[map_idx], gl, g_list); + SLIST_INSERT_HEAD(&glyph_hash[hash], gl, g_hash); glyph_unique++; return (gl);