← Back to branch summary

~ubuntu-branches/ubuntu/vivid/vowpal-wabbit/vivid

« back to all changes in this revision

Viewing changes to vowpalwabbit/cache.cc

  • Committer: Package Import Robot
  • Author(s): Yaroslav Halchenko
  • Date: 2013-08-27 20:52:23 UTC
  • mfrom: (1.2.1) (7.1.2 experimental)
  • Revision ID: package-import@ubuntu.com-20130827205223-q005ps71tqinh25v
Tags: 7.3-1
New upstream release

Show diffs side-by-side

added added

removed removed

Lines of Context:
vowpalwabbit/cache.cc
 
1
/*
 
2
Copyright (c) by respective owners including Yahoo!, Microsoft, and
 
3
individual contributors. All rights reserved.  Released under a BSD (revised)
 
4
license as described in the file LICENSE.
 
5
 */
 
6
#include "cache.h"
 
7
#include "unique_sort.h"
 
8
#include "global_data.h"
 
9
 
 
10
using namespace std;
 
11
 
 
12
const size_t neg_1 = 1;
 
13
const size_t general = 2;
 
14
 
 
15
char* run_len_decode(char *p, uint32_t& i)
 
16
{// read an int 7 bits at a time.
 
17
  size_t count = 0;
 
18
  while(*p & 128)\
 
19
    i = i | ((*(p++) & 127) << 7*count++);
 
20
  i = i | (*(p++) << 7*count);
 
21
  return p;
 
22
}
 
23
 
 
24
inline int32_t ZigZagDecode(uint32_t n) { return (n >> 1) ^ -static_cast<int32_t>(n & 1); }
 
25
 
 
26
size_t read_cached_tag(io_buf& cache, example* ae)
 
27
{
 
28
  char* c;
 
29
  size_t tag_size;
 
30
  if (buf_read(cache, c, sizeof(tag_size)) < sizeof(tag_size))
 
31
    return 0;
 
32
  tag_size = *(size_t*)c;
 
33
  c += sizeof(tag_size);  
 
34
  cache.set(c);
 
35
  if (buf_read(cache, c, tag_size) < tag_size) 
 
36
    return 0;
 
37
  
 
38
  ae->tag.erase();
 
39
  push_many(ae->tag, c, tag_size);
 
40
  return tag_size+sizeof(tag_size);
 
41
}
 
42
 
 
43
struct one_float {
 
44
  float f;
 
45
}
 
46
#ifndef _WIN32
 
47
__attribute__((packed))
 
48
#endif
 
49
        ;
 
50
 
 
51
int read_cached_features(void* in, example* ec)
 
52
{
 
53
  vw* all = (vw*)in;
 
54
  example* ae = (example*)ec;
 
55
  ae->sorted = all->p->sorted_cache;
 
56
  io_buf* input = all->p->input;
 
57
 
 
58
  size_t total = all->p->lp->read_cached_label(all->sd, ae->ld, *input);
 
59
  if (total == 0)
 
60
    return 0;
 
61
  if (read_cached_tag(*input,ae) == 0)
 
62
    return 0;
 
63
  char* c;
 
64
  unsigned char num_indices = 0;
 
65
  if (buf_read(*input, c, sizeof(num_indices)) < sizeof(num_indices)) 
 
66
    return 0;
 
67
  num_indices = *(unsigned char*)c;
 
68
  c += sizeof(num_indices);
 
69
 
 
70
  all->p->input->set(c);
 
71
  for (;num_indices > 0; num_indices--)
 
72
    {
 
73
      size_t temp;
 
74
      unsigned char index = 0;
 
75
      if((temp = buf_read(*input,c,sizeof(index) + sizeof(size_t))) < sizeof(index) + sizeof(size_t)) {
 
76
        cerr << "truncated example! " << temp << " " << char_size + sizeof(size_t) << endl;
 
77
        return 0;
 
78
      }
 
79
 
 
80
      index = *(unsigned char*)c;
 
81
      c+= sizeof(index);
 
82
      ae->indices.push_back((size_t)index);
 
83
      v_array<feature>* ours = ae->atomics+index;
 
84
      float* our_sum_feat_sq = ae->sum_feat_sq+index;
 
85
      size_t storage = *(size_t *)c;
 
86
      c += sizeof(size_t);
 
87
      all->p->input->set(c);
 
88
      total += storage; 
 
89
     if (buf_read(*input,c,storage) < storage) {
 
90
        cerr << "truncated example! wanted: " << storage << " bytes" << endl;
 
91
        return 0;
 
92
      }
 
93
 
 
94
      char *end = c+storage;
 
95
 
 
96
      uint32_t last = 0;
 
97
      
 
98
      for (;c!= end;)
 
99
        {         
 
100
          feature f = {1., 0};
 
101
          c = run_len_decode(c,f.weight_index);
 
102
          if (f.weight_index & neg_1) 
 
103
            f.x = -1.;
 
104
          else if (f.weight_index & general)        {
 
105
              f.x = ((one_float *)c)->f;
 
106
              c += sizeof(float);
 
107
            }
 
108
          *our_sum_feat_sq += f.x*f.x;
 
109
          uint32_t diff = f.weight_index >> 2;
 
110
 
 
111
          int32_t s_diff = ZigZagDecode(diff);
 
112
          if (s_diff < 0)
 
113
            ae->sorted = false;
 
114
          f.weight_index = last + s_diff;
 
115
          last = f.weight_index;
 
116
          ours->push_back(f);
 
117
        }
 
118
      all->p->input->set(c);
 
119
    }
 
120
 
 
121
  return (int)total;
 
122
}
 
123
 
 
124
char* run_len_encode(char *p, size_t i)
 
125
{// store an int 7 bits at a time.
 
126
  while (i >= 128)
 
127
    {
 
128
      *(p++) = (i & 127) | 128;
 
129
      i = i >> 7;
 
130
    }
 
131
  *(p++) = (i & 127);
 
132
  return p;
 
133
}
 
134
 
 
135
inline uint32_t ZigZagEncode(int32_t n) { 
 
136
  uint32_t ret = (n << 1) ^ (n >> 31);
 
137
  return ret;
 
138
}
 
139
 
 
140
void output_byte(io_buf& cache, unsigned char s)
 
141
{
 
142
  char *c;
 
143
  
 
144
  buf_write(cache, c, 1);
 
145
  *(c++) = s;
 
146
  cache.set(c);
 
147
}
 
148
 
 
149
void output_features(io_buf& cache, unsigned char index, feature* begin, feature* end, uint32_t mask)
 
150
{
 
151
  char* c;
 
152
  size_t storage = (end-begin) * int_size;
 
153
  for (feature* i = begin; i != end; i++)
 
154
    if (i->x != 1. && i->x != -1.)
 
155
      storage+=sizeof(float);
 
156
  buf_write(cache, c, sizeof(index) + storage + sizeof(size_t));
 
157
  *(unsigned char*)c = index;
 
158
  c += sizeof(index);
 
159
 
 
160
  char *storage_size_loc = c;
 
161
  c += sizeof(size_t);
 
162
 
 
163
  uint32_t last = 0;
 
164
  
 
165
  for (feature* i = begin; i != end; i++)
 
166
    {
 
167
      uint32_t cache_index = (i->weight_index) & mask;
 
168
      int32_t s_diff = (cache_index - last);
 
169
      size_t diff = ZigZagEncode(s_diff) << 2;
 
170
      last = cache_index;
 
171
      if (i->x == 1.) 
 
172
        c = run_len_encode(c, diff);
 
173
      else if (i->x == -1.) 
 
174
        c = run_len_encode(c, diff | neg_1);
 
175
      else {
 
176
        c = run_len_encode(c, diff | general);
 
177
        *(float *)c = i->x;
 
178
        c += sizeof(float);
 
179
      }
 
180
    }
 
181
  cache.set(c);
 
182
  *(size_t*)storage_size_loc = c - storage_size_loc - sizeof(size_t);  
 
183
}
 
184
 
 
185
void cache_tag(io_buf& cache, v_array<char> tag)
 
186
{
 
187
  char *c;
 
188
  buf_write(cache, c, sizeof(size_t)+tag.size());
 
189
  *(size_t*)c = tag.size();
 
190
  c += sizeof(size_t);
 
191
  memcpy(c, tag.begin, tag.size());
 
192
  c += tag.size();
 
193
  cache.set(c);
 
194
}
 
195
 
 
196
void cache_features(io_buf& cache, example* ae, uint32_t mask)
 
197
{
 
198
  cache_tag(cache,ae->tag);
 
199
  output_byte(cache, (unsigned char) ae->indices.size());
 
200
  for (unsigned char* b = ae->indices.begin; b != ae->indices.end; b++)
 
201
    output_features(cache, *b, ae->atomics[*b].begin,ae->atomics[*b].end, mask);
 
202
}