Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #146537
| Newsgroups | comp.lang.c |
|---|---|
| Date | 2019-10-02 08:00 -0700 |
| References | <qmsqs0$472$1@news.albasani.net> <qn1r0n$b77$1@gioia.aioe.org> <20191002162609.52a3f122331a7c7dd7040fe6@gmail.com> |
| Message-ID | <9fa88375-81de-45bf-a471-2fdc8b3dc86a@googlegroups.com> (permalink) |
| Subject | Re: alloca()-support |
| From | jadill33@gmail.com |
On Wednesday, October 2, 2019 at 9:26:18 AM UTC-4, Anton Shepelev wrote:
> Chris M. Thomasson:
>
> > Well, I have something even more hackish. The region
> > allocator that can be stack based. It can be fed with
> > memory reaped from alloca:
> > http://pastebin.com/raw/f37a23918
>
> I find it hard to comprehend because the code has no
> comments and uses macros extensively. Do I understand
> aright that you have written, as it were, a secondary memory
> manager that uses a C memory block instead of RAM and does
> not support deallocation except by flushing the whole thing?
>
> When is it more convenient than, say, local fixed arrays for
> dynamic structures of limited size?
Here is a snippet of some code I've played with of an algorithm that
uses small buffer optimization using region allocators. The idea is to
trade space for speed by allocating stack space in your algorithm,
attempt to allocate from it and if it fails, switches to use malloc.
Of course with anything like this, you trade simplicity and additional
maintenance costs to try to get more performance, so YMMV.
\code snippet
int r_levenshtein( const char* s1, const char* s2 );
size_t small_buffer_optimization = 0;
struct string_pair
{
char* lhs;
char* rhs;
};
int main( void )
{
int distance;
char tmp_str[40];
size_t idx;
struct string_pair tests[] =
{
{ "kitten", "sitting" },
{ "gamble", "gumbo" },
{ "accomodate", "accommodate" },
{ "mispell", "misspell" },
{ "pasttime", "pastime" },
{ "barbecue", "barbeque" },
{ "beleive", "believe" },
{ "Saturday", "Sunday" },
{ "levenshtein", "meilenstein" },
{ "strawberry", "raspberry" },
{ "null", "" },
{ "", "empty" },
{ "", "" },
{ "identical", "identical" },
};
printf( " -----------------------------------------------------\n" );
printf( "| LHS | RHS | Levenshtein |\n" );
printf( " -----------------------------------------------------\n" );
for ( idx = 0; idx < c_sizeof_array (tests); ++idx )
{
distance = r_levenshtein( tests[idx].lhs, tests[idx].rhs );
snprintf( tmp_str, sizeof (tmp_str), "\"%s\"", tests[idx].lhs );
printf( " %-17s", tests[idx].lhs ? tmp_str : "(null)" );
snprintf( tmp_str, sizeof (tmp_str), "\"%s\"", tests[idx].rhs );
printf( " %-17s", tests[idx].rhs ? tmp_str : "(null)" );
printf( " %d\n", distance );
}
printf( "\n" );
printf( "small buffer optimization count = %" PRIuSIZE "\n",
small_buffer_optimization );
return 0;
}
int r_levenshtein( const char* s1, const char* s2 )
{
int distance;
size_t m, n;
int* proximity_matrix;
struct c_region pm_region;
unsigned char pm_workspace[sizeof (int) * 64];
bool c_malloc_used = false;
c_return_value_if_fail( s1 != NULL, -1 );
c_return_value_if_fail( s2 != NULL, -1 );
m = strlen( s1 );
n = strlen( s2 );
/* If one of the strings is empty "", the edit distance is equal to
the length of the non-empty string. */
if ( m == 0 || n == 0 ) {
return m + n;
}
c_region_initialize( &pm_region, pm_workspace, sizeof pm_workspace );
++m;
++n;
proximity_matrix = c_region_allocate( &pm_region,
sizeof (int) * m * n,
alignof (int) );
if ( proximity_matrix == NULL )
{
proximity_matrix = c_malloc( sizeof (int) * m * n );
c_malloc_used = true;
}
else {
++small_buffer_optimization;
}
if ( proximity_matrix )
{
gc_compute_levenshtein_matrix( proximity_matrix, m, n, s1, s2 );
distance = proximity_matrix[m*n-1];
if ( c_malloc_used ) {
c_free( proximity_matrix );
}
}
else {
distance = -1;
}
return distance;
}
\endcode
Best regards,
John D.
Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
alloca()-support Bonita Montero <Bonita.Montero@gmail.com> - 2019-09-30 14:02 +0200
Re: alloca()-support Bonita Montero <Bonita.Montero@gmail.com> - 2019-09-30 16:09 +0200
Re: alloca()-support Bo Persson <bo@bo-persson.se> - 2019-09-30 17:29 +0200
Re: alloca()-support Bonita Montero <Bonita.Montero@gmail.com> - 2019-09-30 17:33 +0200
Re: alloca()-support Anton Shepelev <anton.txt@g{oogle}mail.com> - 2019-09-30 17:12 +0300
Re: alloca()-support Bonita Montero <Bonita.Montero@gmail.com> - 2019-09-30 16:16 +0200
Re: alloca()-support Anton Shepelev <anton.txt@g{oogle}mail.com> - 2019-09-30 17:30 +0300
Re: alloca()-support Bonita Montero <Bonita.Montero@gmail.com> - 2019-09-30 16:44 +0200
Re: alloca()-support Anton Shepelev <anton.txt@gmail.com> - 2019-10-02 00:36 +0300
Re: alloca()-support Bonita Montero <Bonita.Montero@gmail.com> - 2019-10-02 06:28 +0200
Re: alloca()-support Anton Shepelev <anton.txt@gmail.com> - 2019-10-02 16:08 +0300
Re: alloca()-support Bonita Montero <Bonita.Montero@gmail.com> - 2019-10-02 15:42 +0200
Re: alloca()-support scott@slp53.sl.home (Scott Lurndal) - 2019-09-30 14:30 +0000
Re: alloca()-support Anton Shepelev <anton.txt@g{oogle}mail.com> - 2019-09-30 17:33 +0300
Re: alloca()-support David Brown <david.brown@hesbynett.no> - 2019-09-30 16:56 +0200
Re: alloca()-support Melzzzzz <Melzzzzz@zzzzz.com> - 2019-09-30 15:29 +0000
Re: alloca()-support Bonita Montero <Bonita.Montero@gmail.com> - 2019-09-30 17:31 +0200
Re: alloca()-support Melzzzzz <Melzzzzz@zzzzz.com> - 2019-10-01 07:03 +0000
Re: alloca()-support Bonita Montero <Bonita.Montero@gmail.com> - 2019-10-01 10:57 +0200
Re: alloca()-support Melzzzzz <Melzzzzz@zzzzz.com> - 2019-10-01 18:49 +0000
Re: alloca()-support Bonita Montero <Bonita.Montero@gmail.com> - 2019-10-01 21:20 +0200
Re: alloca()-support scott@slp53.sl.home (Scott Lurndal) - 2019-10-01 20:39 +0000
Re: alloca()-support Melzzzzz <Melzzzzz@zzzzz.com> - 2019-10-02 04:15 +0000
Re: alloca()-support Bonita Montero <Bonita.Montero@gmail.com> - 2019-10-02 06:28 +0200
Re: alloca()-support Melzzzzz <Melzzzzz@zzzzz.com> - 2019-10-02 04:29 +0000
Re: alloca()-support Keith Thompson <kst-u@mib.org> - 2019-09-30 11:14 -0700
Re: alloca()-support Bonita Montero <Bonita.Montero@gmail.com> - 2019-09-30 18:04 +0200
Re: alloca()-support William Ahern <william@25thandClement.com> - 2019-09-30 11:01 -0700
Re: alloca()-support Bonita Montero <Bonita.Montero@gmail.com> - 2019-10-01 07:19 +0200
Re: alloca()-support Paavo Helde <myfirstname@osa.pri.ee> - 2019-09-30 22:26 +0300
Re: alloca()-support scott@slp53.sl.home (Scott Lurndal) - 2019-09-30 19:46 +0000
Re: alloca()-support Bonita Montero <Bonita.Montero@gmail.com> - 2019-10-01 07:32 +0200
Re: alloca()-support Paavo Helde <myfirstname@osa.pri.ee> - 2019-10-01 09:08 +0300
Re: alloca()-support Bonita Montero <Bonita.Montero@gmail.com> - 2019-10-01 08:35 +0200
Re: alloca()-support gazelle@shell.xmission.com (Kenny McCormack) - 2019-09-30 16:26 +0000
Re: alloca()-support Soviet_Mario <SovietMario@CCCP.MIR> - 2019-09-30 18:48 +0200
Re: alloca()-support Bonita Montero <Bonita.Montero@gmail.com> - 2019-09-30 18:51 +0200
Re: alloca()-support Soviet_Mario <SovietMario@CCCP.MIR> - 2019-09-30 18:55 +0200
Re: alloca()-support Bonita Montero <Bonita.Montero@gmail.com> - 2019-09-30 18:58 +0200
Re: alloca()-support Soviet_Mario <SovietMario@CCCP.MIR> - 2019-09-30 19:53 +0200
Re: alloca()-support Keith Thompson <kst-u@mib.org> - 2019-09-30 11:13 -0700
Re: alloca()-support Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-10-06 06:16 -0700
Re: alloca()-support Anton Shepelev <anton.txt@gmail.com> - 2019-10-06 16:22 +0300
Re: alloca()-support Keith Thompson <kst-u@mib.org> - 2019-10-06 12:58 -0700
Re: alloca()-support "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-10-06 13:16 -0700
Re: alloca()-support scott@slp53.sl.home (Scott Lurndal) - 2019-09-30 19:38 +0000
Re: alloca()-support Bonita Montero <Bonita.Montero@gmail.com> - 2019-10-01 07:41 +0200
Re: alloca()-support scott@slp53.sl.home (Scott Lurndal) - 2019-10-01 15:19 +0000
Re: alloca()-support Bonita Montero <Bonita.Montero@gmail.com> - 2019-10-01 17:31 +0200
Re: alloca()-support Melzzzzz <Melzzzzz@zzzzz.com> - 2019-10-01 18:58 +0000
Re: alloca()-support Bonita Montero <Bonita.Montero@gmail.com> - 2019-10-01 21:24 +0200
Re: alloca()-support Melzzzzz <Melzzzzz@zzzzz.com> - 2019-10-02 04:28 +0000
Re: alloca()-support Bonita Montero <Bonita.Montero@gmail.com> - 2019-10-02 06:30 +0200
Re: alloca()-support Melzzzzz <Melzzzzz@zzzzz.com> - 2019-10-02 04:36 +0000
Re: alloca()-support David Brown <david.brown@hesbynett.no> - 2019-10-02 10:01 +0200
Re: alloca()-support Melzzzzz <Melzzzzz@zzzzz.com> - 2019-10-02 04:42 +0000
Re: alloca()-support David Brown <david.brown@hesbynett.no> - 2019-10-02 10:10 +0200
Re: alloca()-support Mel <mel@zzzzz.com> - 2019-10-02 15:13 +0200
Re: alloca()-support David Brown <david.brown@hesbynett.no> - 2019-10-01 21:10 +0200
Re: alloca()-support Bonita Montero <Bonita.Montero@gmail.com> - 2019-10-01 21:25 +0200
Re: alloca()-support scott@slp53.sl.home (Scott Lurndal) - 2019-10-01 20:44 +0000
Re: alloca()-support David Brown <david.brown@hesbynett.no> - 2019-10-01 23:26 +0200
Re: alloca()-support Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2019-10-01 21:08 -0600
Re: alloca()-support David Brown <david.brown@hesbynett.no> - 2019-10-02 10:19 +0200
Re: alloca()-support Bonita Montero <Bonita.Montero@gmail.com> - 2019-10-02 06:39 +0200
Re: alloca()-support David Brown <david.brown@hesbynett.no> - 2019-10-02 10:34 +0200
Re: alloca()-support Mel <mel@zzzzz.com> - 2019-10-02 15:14 +0200
Re: alloca()-support Mel <mel@zzzzz.com> - 2019-10-02 15:18 +0200
Re: alloca()-support Bonita Montero <Bonita.Montero@gmail.com> - 2019-10-02 15:21 +0200
Re: alloca()-support Melzzzzz <Melzzzzz@zzzzz.com> - 2019-10-03 04:09 +0000
Re: alloca()-support Bonita Montero <Bonita.Montero@gmail.com> - 2019-10-03 07:48 +0200
Re: alloca()-support Melzzzzz <Melzzzzz@zzzzz.com> - 2019-10-03 05:49 +0000
Re: alloca()-support Bonita Montero <Bonita.Montero@gmail.com> - 2019-10-03 07:52 +0200
Re: alloca()-support Melzzzzz <Melzzzzz@zzzzz.com> - 2019-10-03 06:46 +0000
Re: alloca()-support Bonita Montero <Bonita.Montero@gmail.com> - 2019-10-03 10:59 +0200
Re: alloca()-support Soviet_Mario <SovietMario@CCCP.MIR> - 2019-10-03 13:39 +0200
Re: alloca()-support scott@slp53.sl.home (Scott Lurndal) - 2019-10-03 13:23 +0000
Re: alloca()-support David Brown <david.brown@hesbynett.no> - 2019-10-03 15:38 +0200
Re: alloca()-support scott@slp53.sl.home (Scott Lurndal) - 2019-10-03 14:51 +0000
Re: alloca()-support David Brown <david.brown@hesbynett.no> - 2019-10-04 09:49 +0200
Re: alloca()-support Soviet_Mario <SovietMario@CCCP.MIR> - 2019-10-03 21:47 +0200
Re: alloca()-support David Brown <david.brown@hesbynett.no> - 2019-10-04 09:53 +0200
Re: alloca()-support Soviet_Mario <SovietMario@CCCP.MIR> - 2019-10-03 21:52 +0200
Re: alloca()-support Bonita Montero <Bonita.Montero@gmail.com> - 2019-10-01 07:39 +0200
Re: alloca()-support James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-09-30 21:36 -0400
Re: alloca()-support Philipp Klaus Krause <pkk@spth.de> - 2019-09-30 19:14 +0200
Re: alloca()-support Bonita Montero <Bonita.Montero@gmail.com> - 2019-09-30 19:16 +0200
Re: alloca()-support Robert Wessel <robertwessel2@yahoo.com> - 2019-10-01 00:18 -0500
Re: alloca()-support Bonita Montero <Bonita.Montero@gmail.com> - 2019-10-01 07:43 +0200
Re: alloca()-support Keith Thompson <kst-u@mib.org> - 2019-10-01 02:42 -0700
Re: alloca()-support James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-10-01 08:11 -0400
Re: alloca()-support Bonita Montero <Bonita.Montero@gmail.com> - 2019-10-01 14:53 +0200
Re: alloca()-support scott@slp53.sl.home (Scott Lurndal) - 2019-09-30 17:52 +0000
Re: alloca()-support Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2019-09-30 11:20 -0600
Re: alloca()-support Bonita Montero <Bonita.Montero@gmail.com> - 2019-09-30 19:42 +0200
Re: alloca()-support Soviet_Mario <SovietMario@CCCP.MIR> - 2019-09-30 20:02 +0200
Re: alloca()-support Soviet_Mario <SovietMario@CCCP.MIR> - 2019-09-30 19:54 +0200
Re: alloca()-support Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2019-09-30 14:28 -0600
Re: alloca()-support David Brown <david.brown@hesbynett.no> - 2019-10-01 09:38 +0200
Re: alloca()-support Soviet_Mario <SovietMario@CCCP.MIR> - 2019-09-30 20:01 +0200
Re: alloca()-support Manfred <noname@add.invalid> - 2019-10-01 17:45 +0200
Re: alloca()-support "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-10-02 02:35 -0700
Re: alloca()-support Anton Shepelev <anton.txt@gmail.com> - 2019-10-02 16:26 +0300
Re: alloca()-support jadill33@gmail.com - 2019-10-02 08:00 -0700
Re: alloca()-support Anton Shepelev <anton.txt@gmail.com> - 2019-10-03 02:38 +0300
Re: alloca()-support jadill33@gmail.com - 2019-10-03 08:42 -0700
Re: alloca()-support "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-10-02 12:33 -0700
Re: alloca()-support Anton Shepelev <anton.txt@gmail.com> - 2019-10-03 01:47 +0300
Re: alloca()-support "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-10-05 14:08 -0700
csiph-web