Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #148276
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: OT: improve this simple algorithm? |
| Date | 2019-11-14 15:38 +0100 |
| Organization | albasani.net |
| Message-ID | <qqjost$74a$1@news.albasani.net> (permalink) |
| References | (12 earlier) <7cazF.64737$5W6.28259@fx13.am4> <qqjf8f$4dq$1@dont-email.me> <ELbzF.37452$3T6.9962@fx05.am4> <qqjkcj$po$1@dont-email.me> <hwdzF.571693$7ei.96104@fx36.am4> |
> However a VLA has extra issues: on Windows where gcc uses a function to
> allocate stack frames which are either over 4KB, or which might be over
> 4KB (eg. a VLA of size n, even if n is small), that can make things slower.
I've benchmarked alloca(), and VLAs would have a similar performance
-impact. an alloca() takes about 13 clock-cycles including the __chkstk
on my Ryzen. That should be unbeatable by malloc().
#include <iostream>
#include <cstdlib>
#include <random>
#include <chrono>
#if defined(_MSC_VER)
#include <malloc.h>
#elif defined(__linux__)
#include <alloca.h>
#endif
using namespace std;
using namespace chrono;
void allocaFn( size_t *sizes, size_t n )
{
char volatile *p;
for( size_t i = 0; i != n; ++i )
p = (char volatile *)alloca( sizes[i] ),
*p = '*';
}
int main( int argc, char **argv )
{
if( argc < 2 )
return EXIT_FAILURE;
double clocksPerNs = 1.0 / atof( argv[1] );
size_t const ALLOCATIONS_PER_SLICE = 16,
SLICES = 1024;
size_t sizes[ALLOCATIONS_PER_SLICE * SLICES];
size_t const ROUNDS = 100'000;
size_t const LOWER_LIMIT = 1,
UPPER_KIMIT = 32768;
random_device rd;
uniform_int_distribution<size_t> sizeGen( LOWER_LIMIT, UPPER_KIMIT );
for( size_t &s : sizes )
s = sizeGen( rd );
time_point<high_resolution_clock> start = high_resolution_clock::now();
for( size_t round = ROUNDS; round; --round )
for( size_t slice = 0; slice != SLICES * ALLOCATIONS_PER_SLICE;
slice += ALLOCATIONS_PER_SLICE )
allocaFn( sizes + slice, ALLOCATIONS_PER_SLICE );
double nsPerAllocation = duration_cast<nanoseconds>(
high_resolution_clock::now() - start ).count() / ((double)ROUNDS *
ALLOCATIONS_PER_SLICE * SLICES);
cout << nsPerAllocation / clocksPerNs << " clock cycles" << endl;
}
> char buffer[2048];
> char *t;
> if (length<sizeof(buffer)
> t=buffer;
> else
> t=malloc(length+1);
That's less convenient as my C++-class:
#pragma once
#include <cstddef>
#include <memory>
#include <vector>
#include <cassert>
template<typename T, std::size_t N, typename Alloc = std::allocator<T>>
struct overflow_array
{
overflow_array( std::size_t n, Alloc const &alloc = Alloc() );
~overflow_array();
T &operator []( std::size_t i );
T &front();
T &back();
T *data();
T *begin();
T *end();
T const *cbegin() const;
T const *cend() const;
private:
union
{
T m_array[N];
std::vector<T, Alloc> m_vec;
};
T *m_begin,
*m_end;
};
template<typename T, std::size_t N, typename Alloc>
inline
overflow_array<T, N, Alloc>::overflow_array( std::size_t n, Alloc const
&alloc )
{
if( n <= N )
{
m_begin = m_array;
m_end = m_array + n;
return;
}
new( (void *)&m_vec ) std::vector<T, Alloc>( alloc );
try
{
m_vec.resize( n );
}
catch( ... )
{
m_vec.~vector();
throw;
}
assert((void *)&*m_vec.begin() != (void *)&m_vec);
m_begin = &*m_vec.begin();
m_end = &*m_vec.end();
}
template<typename T, std::size_t N, typename Alloc>
inline
overflow_array<T, N, Alloc>::~overflow_array()
{
if( m_begin == m_array )
return;
m_vec.~vector();
}
template<typename T, std::size_t N, typename Alloc>
inline
T &overflow_array<T, N, Alloc>::operator []( std::size_t i )
{
return m_begin[i];
}
template<typename T, std::size_t N, typename Alloc>
inline
T &overflow_array<T, N, Alloc>::front()
{
return *m_begin;
}
template<typename T, std::size_t N, typename Alloc>
inline
T &overflow_array<T, N, Alloc>::back()
{
return m_end[-1];
}
template<typename T, std::size_t N, typename Alloc>
inline
T *overflow_array<T, N, Alloc>::data()
{
return m_begin;
}
template<typename T, std::size_t N, typename Alloc>
inline
T *overflow_array<T, N, Alloc>::begin()
{
return m_begin;
}
template<typename T, std::size_t N, typename Alloc>
inline
T *overflow_array<T, N, Alloc>::end()
{
return m_end;
}
template<typename T, std::size_t N, typename Alloc>
inline
T const *overflow_array<T, N, Alloc>::cbegin() const
{
return m_begin;
}
template<typename T, std::size_t N, typename Alloc>
inline
T const *overflow_array<T, N, Alloc>::cend() const
{
return m_end;
}
Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
OT: improve this simple algorithm? DFS <nospam@dfs.com> - 2019-11-12 15:55 -0500
Re: OT: improve this simple algorithm? Bart <bc@freeuk.com> - 2019-11-12 21:20 +0000
Re: OT: improve this simple algorithm? DFS <nospam@dfs.com> - 2019-11-12 23:28 -0500
Re: OT: improve this simple algorithm? David Brown <david.brown@hesbynett.no> - 2019-11-13 10:52 +0100
Re: OT: improve this simple algorithm? DFS <nospam@dfs.com> - 2019-11-13 10:16 -0500
Re: OT: improve this simple algorithm? David Brown <david.brown@hesbynett.no> - 2019-11-13 16:53 +0100
Re: OT: improve this simple algorithm? Bart <bc@freeuk.com> - 2019-11-13 11:18 +0000
Re: OT: improve this simple algorithm? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-11-12 23:30 +0000
Re: OT: improve this simple algorithm? Ian Collins <ian-news@hotmail.com> - 2019-11-15 05:12 +1300
Re: OT: improve this simple algorithm? Bart <bc@freeuk.com> - 2019-11-14 16:34 +0000
Re: OT: improve this simple algorithm? Ian Collins <ian-news@hotmail.com> - 2019-11-15 10:07 +1300
Re: OT: improve this simple algorithm? Bart <bc@freeuk.com> - 2019-11-14 22:25 +0000
Re: OT: improve this simple algorithm? Ian Collins <ian-news@hotmail.com> - 2019-11-15 12:02 +1300
Re: OT: improve this simple algorithm? Bart <bc@freeuk.com> - 2019-11-14 23:27 +0000
Re: OT: improve this simple algorithm? Ian Collins <ian-news@hotmail.com> - 2019-11-15 19:06 +1300
Re: OT: improve this simple algorithm? Bart <bc@freeuk.com> - 2019-11-15 10:45 +0000
Re: OT: improve this simple algorithm? David Brown <david.brown@hesbynett.no> - 2019-11-15 13:28 +0100
Re: OT: improve this simple algorithm? Bart <bc@freeuk.com> - 2019-11-15 12:58 +0000
Re: OT: improve this simple algorithm? David Brown <david.brown@hesbynett.no> - 2019-11-15 15:39 +0100
Re: OT: improve this simple algorithm? Bart <bc@freeuk.com> - 2019-11-15 15:04 +0000
Re: OT: improve this simple algorithm? Richard Damon <Richard@Damon-Family.org> - 2019-11-15 12:19 -0500
Re: OT: improve this simple algorithm? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-11-15 09:46 -0800
Re: OT: improve this simple algorithm? Bart <bc@freeuk.com> - 2019-11-15 18:59 +0000
Re: OT: improve this simple algorithm? Bart <bc@freeuk.com> - 2019-11-16 11:59 +0000
Re: OT: improve this simple algorithm? Ian Collins <ian-news@hotmail.com> - 2019-11-16 09:02 +1300
Re: OT: improve this simple algorithm? David Brown <david.brown@hesbynett.no> - 2019-11-15 11:17 +0100
Re: OT: improve this simple algorithm? Jorgen Grahn <grahn+nntp@snipabacken.se> - 2019-11-15 21:38 +0000
Re: OT: improve this simple algorithm? DFS <nospam@dfs.com> - 2019-11-14 11:44 -0500
Re: OT: improve this simple algorithm? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-11-14 18:11 +0000
Re: OT: improve this simple algorithm? DFS <nospam@dfs.com> - 2019-11-14 13:33 -0500
Re: OT: improve this simple algorithm? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-11-15 01:49 +0000
Re: OT: improve this simple algorithm? Barry Schwarz <schwarzb@delq.com> - 2019-11-14 10:38 -0800
Re: OT: improve this simple algorithm? DFS <nospam@dfs.com> - 2019-11-14 12:56 -0500
Re: OT: improve this simple algorithm? James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-11-14 13:50 -0500
Re: OT: improve this simple algorithm? DFS <nospam@dfs.com> - 2019-11-14 14:42 -0500
Re: OT: improve this simple algorithm? James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-11-14 15:25 -0500
Re: OT: improve this simple algorithm? Barry Schwarz <schwarzb@delq.com> - 2019-11-14 11:03 -0800
Re: OT: improve this simple algorithm? DFS <nospam@dfs.com> - 2019-11-14 16:08 -0500
Re: OT: improve this simple algorithm? David Brown <david.brown@hesbynett.no> - 2019-11-15 11:30 +0100
Re: OT: improve this simple algorithm? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-11-15 11:17 +0000
Re: OT: improve this simple algorithm? DFS <nospam@dfs.com> - 2019-11-15 17:35 -0500
Re: OT: improve this simple algorithm? DFS <nospam@dfs.com> - 2019-11-15 17:39 -0500
Re: OT: improve this simple algorithm? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-11-15 23:19 +0000
Re: OT: improve this simple algorithm? DFS <nospam@dfs.com> - 2019-11-15 18:53 -0500
Re: OT: improve this simple algorithm? Richard Damon <Richard@Damon-Family.org> - 2019-11-15 19:08 -0500
Re: OT: improve this simple algorithm? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-11-16 01:30 +0000
Re: OT: improve this simple algorithm? James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-11-16 07:39 -0500
Re: OT: improve this simple algorithm? James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-11-16 07:37 -0500
Re: OT: improve this simple algorithm? James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-11-15 09:46 -0500
Re: OT: improve this simple algorithm? Richard Damon <Richard@Damon-Family.org> - 2019-11-15 12:38 -0500
Re: OT: improve this simple algorithm? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-11-15 23:07 +0000
Re: OT: improve this simple algorithm? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-11-28 16:54 -0800
Re: OT: improve this simple algorithm? Richard Damon <Richard@Damon-Family.org> - 2019-11-28 20:17 -0500
Re: OT: improve this simple algorithm? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-11-29 06:08 -0800
Re: OT: improve this simple algorithm? David Brown <david.brown@hesbynett.no> - 2019-11-14 20:45 +0100
Re: OT: improve this simple algorithm? Keith Thompson <kst-u@mib.org> - 2019-11-14 10:10 -0800
Re: OT: improve this simple algorithm? David Brown <david.brown@hesbynett.no> - 2019-11-14 20:19 +0100
Re: OT: improve this simple algorithm? DFS <nospam@dfs.com> - 2019-11-12 23:57 -0500
Re: OT: improve this simple algorithm? David Brown <david.brown@hesbynett.no> - 2019-11-13 10:34 +0100
Re: OT: improve this simple algorithm? DFS <nospam@dfs.com> - 2019-11-13 23:57 -0500
Re: OT: improve this simple algorithm? Barry Schwarz <schwarzb@delq.com> - 2019-11-13 23:00 -0800
Re: OT: improve this simple algorithm? Ike Naar <ike@sdf.lonestar.org> - 2019-11-14 07:53 +0000
Re: OT: improve this simple algorithm? guinness.tony@gmail.com - 2019-11-14 02:34 -0800
Re: OT: improve this simple algorithm? David Brown <david.brown@hesbynett.no> - 2019-11-14 10:01 +0100
Re: OT: improve this simple algorithm? Bart <bc@freeuk.com> - 2019-11-14 11:27 +0000
Re: OT: improve this simple algorithm? David Brown <david.brown@hesbynett.no> - 2019-11-14 12:46 +0100
Re: OT: improve this simple algorithm? Bart <bc@freeuk.com> - 2019-11-14 12:01 +0000
Re: OT: improve this simple algorithm? David Brown <david.brown@hesbynett.no> - 2019-11-14 14:05 +0100
Re: OT: improve this simple algorithm? Barry Schwarz <schwarzb@delq.com> - 2019-11-12 18:34 -0800
Re: OT: improve this simple algorithm? Keith Thompson <kst-u@mib.org> - 2019-11-12 19:01 -0800
Re: OT: improve this simple algorithm? David Brown <david.brown@hesbynett.no> - 2019-11-14 17:08 +0100
Re: OT: improve this simple algorithm? Bart <bc@freeuk.com> - 2019-11-14 17:06 +0000
Re: OT: improve this simple algorithm? Bart <bc@freeuk.com> - 2019-11-14 19:11 +0000
Re: OT: improve this simple algorithm? Ian Collins <ian-news@hotmail.com> - 2019-11-15 05:15 +1300
Re: OT: improve this simple algorithm? Bart <bc@freeuk.com> - 2019-11-14 18:13 +0000
Re: OT: improve this simple algorithm? Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-14 20:16 +0100
Re: OT: improve this simple algorithm? Bart <bc@freeuk.com> - 2019-11-14 20:03 +0000
Re: OT: improve this simple algorithm? Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-15 04:51 +0100
Re: OT: improve this simple algorithm? Keith Thompson <kst-u@mib.org> - 2019-11-14 10:15 -0800
Re: OT: improve this simple algorithm? David Brown <david.brown@hesbynett.no> - 2019-11-14 20:52 +0100
Re: OT: improve this simple algorithm? David Brown <david.brown@hesbynett.no> - 2019-11-13 10:57 +0100
Re: OT: improve this simple algorithm? Ian Collins <ian-news@hotmail.com> - 2019-11-13 23:23 +1300
Re: OT: improve this simple algorithm? Bart <bc@freeuk.com> - 2019-11-13 11:53 +0000
Re: OT: improve this simple algorithm? David Brown <david.brown@hesbynett.no> - 2019-11-13 14:02 +0100
Re: OT: improve this simple algorithm? Bart <bc@freeuk.com> - 2019-11-13 13:40 +0000
Re: OT: improve this simple algorithm? David Brown <david.brown@hesbynett.no> - 2019-11-13 17:01 +0100
Re: OT: improve this simple algorithm? Bart <bc@freeuk.com> - 2019-11-13 16:28 +0000
Re: OT: improve this simple algorithm? David Brown <david.brown@hesbynett.no> - 2019-11-13 22:49 +0100
Re: OT: improve this simple algorithm? Bart <bc@freeuk.com> - 2019-11-13 22:38 +0000
Re: OT: improve this simple algorithm? Bart <bc@freeuk.com> - 2019-11-13 23:06 +0000
Re: OT: improve this simple algorithm? David Brown <david.brown@hesbynett.no> - 2019-11-14 10:10 +0100
Re: OT: improve this simple algorithm? Bart <bc@freeuk.com> - 2019-11-14 10:42 +0000
Re: OT: improve this simple algorithm? David Brown <david.brown@hesbynett.no> - 2019-11-14 12:53 +0100
Re: OT: improve this simple algorithm? Bart <bc@freeuk.com> - 2019-11-14 12:28 +0000
Re: OT: improve this simple algorithm? David Brown <david.brown@hesbynett.no> - 2019-11-14 14:21 +0100
Re: OT: improve this simple algorithm? Bart <bc@freeuk.com> - 2019-11-14 14:28 +0000
Re: OT: improve this simple algorithm? Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-14 15:38 +0100
Re: OT: improve this simple algorithm? Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-14 13:37 +0100
Re: OT: improve this simple algorithm? Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-14 13:38 +0100
Re: OT: improve this simple algorithm? Thiago Adams <thiago.adams@gmail.com> - 2019-11-13 05:21 -0800
csiph-web