From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mr85p00im-hyfv06011401.me.com (mr85p00im-hyfv06011401.me.com [17.58.23.191]) by sourceware.org (Postfix) with ESMTPS id A14C73858D32 for ; Wed, 17 Aug 2022 07:49:42 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org A14C73858D32 Received: from [192.168.1.6] (mr38p00im-dlb-asmtp-mailmevip.me.com [17.57.152.18]) by mr85p00im-hyfv06011401.me.com (Postfix) with ESMTPSA id 4C7CF357B0CD; Wed, 17 Aug 2022 07:49:40 +0000 (UTC) Message-ID: <71057c8f-8850-dde1-1a69-2a23ac06f099@mac.com> Date: Wed, 17 Aug 2022 19:49:37 +1200 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.13; rv:91.0) Gecko/20100101 Thunderbird/91.12.0 Subject: Re: [RFC] zip_vector: in-memory block compression of integer arrays Content-Language: en-US To: Richard Biener Cc: GCC Mailing List References: <80497d16-0942-1f45-fd0e-e65a971d60aa@mac.com> From: Michael Clark In-Reply-To: Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit X-Proofpoint-ORIG-GUID: L4vd8YSn8C9HJdrkcT-l5tVcpW5BObNC X-Proofpoint-GUID: L4vd8YSn8C9HJdrkcT-l5tVcpW5BObNC X-Proofpoint-Virus-Version: =?UTF-8?Q?vendor=3Dfsecure_engine=3D1.1.170-22c6f66c430a71ce266a39bfe25bc?= =?UTF-8?Q?2903e8d5c8f:6.0.138,18.0.572,17.0.605.474.0000000_definitions?= =?UTF-8?Q?=3D2020-02-14=5F11:2020-02-14=5F02,2020-02-14=5F11,2020-01-23?= =?UTF-8?Q?=5F02_signatures=3D0?= X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 suspectscore=0 malwarescore=0 phishscore=0 clxscore=1011 mlxscore=0 spamscore=0 bulkscore=0 adultscore=0 mlxlogscore=999 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2206140000 definitions=main-2208170032 X-Spam-Status: No, score=-4.2 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, NICE_REPLY_A, RCVD_IN_DNSWL_LOW, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 17 Aug 2022 07:49:46 -0000 On 17/08/22 7:10 pm, Richard Biener wrote: >> Q. Why is it specifically of interest to GCC developers? >> >> I think the best way to answer this is with questions. How can we model >> a block-based iterator for a sparse array that is amenable to vectorization? >> >> There are aspects to the zip_vector iterator design that are *not done >> yet* concerning its current implementation. The iteration has two >> phases. There is an inter-block phase at the boundary of each block (the >> logic inside of `switch_page`) that scans and compresses the previously >> active block, updates the page index, and decompresses the next block. >> Then there is a _broad-phase_ for intra-block accesses, which is >> amenable to vectorization due to the use of fixed-size blocks. >> >> *Making 1D iteration as fast as 2D iteration* >> >> Firstly I have to say that there is a lot of analysis for the >> optimization of the iterator that I would like to discuss. There is the >> issue of hoisting the inter-block boundary test from the fast path so >> that during block boundary traversal, subsequent block endings are >> calculated in advance so that the broad phase only requires a pointer >> increment and comparison with the addresses held in registers. >> >> The challenge is getting past compiler alias analysis. Alias analysis >> seems to prevent caching of the sum of the slab base address and active >> area offset in a register versus being demoted to memory accesses. These >> member variables hold the location of the slab and the offset to the >> uncompressed page which are both on the critical path. When these values >> are in memory, _it adds 4 or more cycles of latency for base address >> calculation on every access_. There is also the possibility to hoist and >> fold the active page check as we know we can make constructive proofs >> concerning changes to that value. >> >> Benchmarks compare the performance of 1D and 2D style iterators. At >> certain times the compiler would hoist the base and offset pointers from >> member variable accesses into registers in the 1D version making a >> noticeable difference in performance. In some respects, from the >> perspective of single-threaded code, the only way the pointer to the >> active region can change is inside `switch_page(size_t y)`. >> >> The potential payoff is huge because one may be able to access data ~ >> 0.9X - 3.5X faster than simply accessing integers in RAM when combining >> the reduction in global memory bandwidth with auto-vectorization, but >> the challenge is generating safe code for the simpler 1D iteration case >> that is as efficient as explicit 2D iteration. >> >> 1D iteration: >> >> for (auto x : vec) x2 += x; >> >> 2D iteration: >> >> for (size_t i = 0; i < n; i += decltype(vec)::page_interval) { >> i64 *cur = &vec[i], *end = cur + decltype(vec)::page_interval; >> while(cur != end) x2 += *cur++; >> } >> >> Note: In this example, I avoid having a different size loop tail but >> that is also a consideration. >> >> I trialled several techniques using a simplified version of the >> `zip_vector` class where `switch_page` was substituted with simple logic >> so that it was possible to get the compiler to coalesce the slab base >> pointer and active area offset into a single calculation upon page >> crossings. There is also hoisting of the active_page check >> (_y-parameter_) to only occur on block crossings. I found that when the >> `switch_page` implementation became more complex, i.e. probably adding >> an extern call to `malloc`, the compiler would resort to more >> conservatively fetching through a pointer to a member variable for the >> base pointer and offset calculation. See here: >> >> https://github.com/metaparadigm/zvec/blob/756e583472028fcc36e94c0519926978094dbb00/src/zip_vector.h#L491-L496 >> >> So I got to the point where I thought it would help to get input from >> compiler developers to figure out how to observe which internal >> constraints are violated by "switch_page" preventing the base pointer >> and offset address calculation from being cached in registers. >> "slab_data" and "active_area" are neither volatile nor atomic, so >> threads should not expect their updates to be atomic or go through memory. >> >> I tried a large number of small experiments. e.g. so let's try and >> collapse "slab_data" and "active_area" into one pointer at the end of >> "switch_page" so that we only have one pointer to access. Also, the >> "active_page" test doesn't necessarily need to be in the broad phase. I >> had attempted to manually hoist these variables by modifying the >> iterators but found it was necessary to keep them where they were to >> avoid introducing stateful invariants to the iterators that could become >> invalidated due to read accesses. >> >> Stack/register-based coroutines could help due to the two distinct >> states in the iterator. >> >> I want to say that it is not as simple as one might think on the >> surface. I tried several approaches to coalesce address calculations and >> move them into the page switch logic, all leading to performance >> fall-off, almost like the compiler was carrying some pessimization that >> forced touched member variables to be accessed via memory versus >> registers. At one stage the 1D form was going fast with GCC, but after >> adding support for `zip_vector` and `zip_vector`, I found that >> performance fell off. So I would like to observe exactly which code >> causes pessimization of accesses to member variables, preventing them >> from being held in registers and causing accesses to go to memory >> instead. It seems it should be possible to get 1D iteration to be faster >> than _std::vector_ as I did witness this with GCC but the optimization >> does not seem to be stable. >> >> So that's what I would like help with... > > It's difficult to sort through a maze of C++ abstraction, it also means > that it's probably difficult if not impossible to place a strathegic > __restrict somewhere (GCC only likes that on function arguments). > > TBAA is difficult to deal with, especially if you have integer data > and integer iterator state. There's currently no way to make > primitive types with different alias sets (typedefs and friends do > not help). I didn't suspect it was an easy problem to solve but I think it is a useful problem to solve. I had considered if one had a co-routine perhaps the compiler would have clear blocks it can more easily analyze what can potentially change within the scope of a block, where the "block-crossing logic" has a clear cut with the "intra-block logic". A co-routine could cut the control flow to hold the intra-block state where we just increment a pointer. Google's Highway library does indeed generate somewhat of a maze of code that is possibly not the easiest to analyze compared to say using the non portable AVX intrinsics or one of the fixed width SIMD libraries. However, if you look at the zvec code, I had some awareness of this and made some cuts where I expose the codecs through a simple set of high-level interfaces that do indeed use __restrict. In fact I don't think they are necessarily the problem. In any case there is a distinct cut between the combinatorial expansion of low-level compression codecs, because we access them via function pointers so that we can do cpuid based dispatch. It wouldn't be too hard to make a purely C API for them. if you look in zvec_block.h we have the high level block codec API (could be made C in a pinch). the headers do indeed have __restrict. I feel like I there might be a problem with realloc or something else. /* * high-level interface to scan, encode, and decode blocks * * - scan block for statistics with codec * zvec_stats zvec_block_scan(T * in, size_t n, zvec_codec codec); * * - select block codec and size from statistics * zvec_format zvec_block_format(zvec_stats s); * * - gather block iv and delta from statistics * zvec_meta zvec_block_metadata(zvec_stats s); * * - block size from format * size_t zvec_block_size(zvec_format fmt, size_t n); * * - block alignment from format * size_t zvec_block_align(zvec_format fmt, size_t n); * * - encode block using metadata * void zvec_block_encode(T * in, void * comp, size_t n, * zvec_format fmt, zvec_meta meta); * * - decode block using metadata * void zvec_block_decode(T * out, void * comp, size_t n, * zvec_format fmt, zvec_meta meta); */