Mercurial > hg > truffle

comparison src/share/vm/memory/binaryTreeDictionary.cpp @ 8001:db9981fd3124

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
8005915: Unify SERIALGC and INCLUDE_ALTERNATE_GCS Summary: Rename INCLUDE_ALTERNATE_GCS to INCLUDE_ALL_GCS and replace SERIALGC with INCLUDE_ALL_GCS. Reviewed-by: coleenp, stefank
author jprovino
date Wed, 23 Jan 2013 13:02:39 -0500
parents e51c9860cf66
children 3c9bc17b9403
comparison
equal deleted inserted replaced
7619:46e60405583b 8001:db9981fd3124
21 * questions. 21 * questions.
22 * 22 *
23 */ 23 */
24 24
25 #include "precompiled.hpp" 25 #include "precompiled.hpp"
26 #include "utilities/macros.hpp"
26 #include "gc_implementation/shared/allocationStats.hpp" 27 #include "gc_implementation/shared/allocationStats.hpp"
27 #include "memory/binaryTreeDictionary.hpp" 28 #include "memory/binaryTreeDictionary.hpp"
28 #include "memory/freeList.hpp" 29 #include "memory/freeList.hpp"
29 #include "memory/freeBlockDictionary.hpp" 30 #include "memory/freeBlockDictionary.hpp"
30 #include "memory/metablock.hpp" 31 #include "memory/metablock.hpp"
31 #include "memory/metachunk.hpp" 32 #include "memory/metachunk.hpp"
32 #include "runtime/globals.hpp" 33 #include "runtime/globals.hpp"
33 #include "utilities/ostream.hpp" 34 #include "utilities/ostream.hpp"
34 #ifndef SERIALGC 35 #include "utilities/macros.hpp"
36 #if INCLUDE_ALL_GCS
35 #include "gc_implementation/concurrentMarkSweep/adaptiveFreeList.hpp" 37 #include "gc_implementation/concurrentMarkSweep/adaptiveFreeList.hpp"
36 #include "gc_implementation/concurrentMarkSweep/freeChunk.hpp" 38 #include "gc_implementation/concurrentMarkSweep/freeChunk.hpp"
37 #include "gc_implementation/shared/spaceDecorator.hpp" 39 #include "gc_implementation/shared/spaceDecorator.hpp"
38 #include "gc_implementation/concurrentMarkSweep/freeChunk.hpp" 40 #include "gc_implementation/concurrentMarkSweep/freeChunk.hpp"
39 #endif // SERIALGC 41 #endif // INCLUDE_ALL_GCS
40 42
41 //////////////////////////////////////////////////////////////////////////////// 43 ////////////////////////////////////////////////////////////////////////////////
42 // A binary tree based search structure for free blocks. 44 // A binary tree based search structure for free blocks.
43 // This is currently used in the Concurrent Mark&Sweep implementation. 45 // This is currently used in the Concurrent Mark&Sweep implementation.
44 //////////////////////////////////////////////////////////////////////////////// 46 ////////////////////////////////////////////////////////////////////////////////
116 TreeList<Chunk_t, FreeList_t>* tl = TreeList<Chunk_t, FreeList_t>::as_TreeList(tc); 118 TreeList<Chunk_t, FreeList_t>* tl = TreeList<Chunk_t, FreeList_t>::as_TreeList(tc);
117 return tl; 119 return tl;
118 } 120 }
119 121
120 122
121 #ifndef SERIALGC 123 #if INCLUDE_ALL_GCS
122 // Specialize for AdaptiveFreeList which tries to avoid 124 // Specialize for AdaptiveFreeList which tries to avoid
123 // splitting a chunk of a size that is under populated in favor of 125 // splitting a chunk of a size that is under populated in favor of
124 // an over populated size. The general get_better_list() just returns 126 // an over populated size. The general get_better_list() just returns
125 // the current list. 127 // the current list.
126 template <> 128 template <>
158 } 160 }
159 } 161 }
160 } 162 }
161 return curTL; 163 return curTL;
162 } 164 }
163 #endif // SERIALGC 165 #endif // INCLUDE_ALL_GCS
164 166
165 template <class Chunk_t, template <class> class FreeList_t> 167 template <class Chunk_t, template <class> class FreeList_t>
166 TreeList<Chunk_t, FreeList_t>* 168 TreeList<Chunk_t, FreeList_t>*
167 TreeList<Chunk_t, FreeList_t>::get_better_list( 169 TreeList<Chunk_t, FreeList_t>::get_better_list(
168 BinaryTreeDictionary<Chunk_t, FreeList_t>* dictionary) { 170 BinaryTreeDictionary<Chunk_t, FreeList_t>* dictionary) {
869 } 871 }
870 872
871 template <class Chunk_t, template <class> class FreeList_t> 873 template <class Chunk_t, template <class> class FreeList_t>
872 void BinaryTreeDictionary<Chunk_t, FreeList_t>::dict_census_update(size_t size, bool split, bool birth){} 874 void BinaryTreeDictionary<Chunk_t, FreeList_t>::dict_census_update(size_t size, bool split, bool birth){}
873 875
874 #ifndef SERIALGC 876 #if INCLUDE_ALL_GCS
875 template <> 877 template <>
876 void BinaryTreeDictionary<FreeChunk, AdaptiveFreeList>::dict_census_update(size_t size, bool split, bool birth){ 878 void BinaryTreeDictionary<FreeChunk, AdaptiveFreeList>::dict_census_update(size_t size, bool split, bool birth){
877 TreeList<FreeChunk, AdaptiveFreeList>* nd = find_list(size); 879 TreeList<FreeChunk, AdaptiveFreeList>* nd = find_list(size);
878 if (nd) { 880 if (nd) {
879 if (split) { 881 if (split) {
898 // This is a death where the appropriate list is now 900 // This is a death where the appropriate list is now
899 // empty and has been removed from the list. 901 // empty and has been removed from the list.
900 // This is a birth associated with a LinAB. The chunk 902 // This is a birth associated with a LinAB. The chunk
901 // for the LinAB is not in the dictionary. 903 // for the LinAB is not in the dictionary.
902 } 904 }
903 #endif // SERIALGC 905 #endif // INCLUDE_ALL_GCS
904 906
905 template <class Chunk_t, template <class> class FreeList_t> 907 template <class Chunk_t, template <class> class FreeList_t>
906 bool BinaryTreeDictionary<Chunk_t, FreeList_t>::coal_dict_over_populated(size_t size) { 908 bool BinaryTreeDictionary<Chunk_t, FreeList_t>::coal_dict_over_populated(size_t size) {
907 // For the general type of freelists, encourage coalescing by 909 // For the general type of freelists, encourage coalescing by
908 // returning true. 910 // returning true.
909 return true; 911 return true;
910 } 912 }
911 913
912 #ifndef SERIALGC 914 #if INCLUDE_ALL_GCS
913 template <> 915 template <>
914 bool BinaryTreeDictionary<FreeChunk, AdaptiveFreeList>::coal_dict_over_populated(size_t size) { 916 bool BinaryTreeDictionary<FreeChunk, AdaptiveFreeList>::coal_dict_over_populated(size_t size) {
915 if (FLSAlwaysCoalesceLarge) return true; 917 if (FLSAlwaysCoalesceLarge) return true;
916 918
917 TreeList<FreeChunk, AdaptiveFreeList>* list_of_size = find_list(size); 919 TreeList<FreeChunk, AdaptiveFreeList>* list_of_size = find_list(size);
918 // None of requested size implies overpopulated. 920 // None of requested size implies overpopulated.
919 return list_of_size == NULL || list_of_size->coal_desired() <= 0 || 921 return list_of_size == NULL || list_of_size->coal_desired() <= 0 ||
920 list_of_size->count() > list_of_size->coal_desired(); 922 list_of_size->count() > list_of_size->coal_desired();
921 } 923 }
922 #endif // SERIALGC 924 #endif // INCLUDE_ALL_GCS
923 925
924 // Closures for walking the binary tree. 926 // Closures for walking the binary tree.
925 // do_list() walks the free list in a node applying the closure 927 // do_list() walks the free list in a node applying the closure
926 // to each free chunk in the list 928 // to each free chunk in the list
927 // do_tree() walks the nodes in the binary tree applying do_list() 929 // do_tree() walks the nodes in the binary tree applying do_list()
977 _inter_sweep_estimate(inter_sweep_estimate), 979 _inter_sweep_estimate(inter_sweep_estimate),
978 _intra_sweep_estimate(intra_sweep_estimate) { } 980 _intra_sweep_estimate(intra_sweep_estimate) { }
979 981
980 void do_list(FreeList<Chunk_t>* fl) {} 982 void do_list(FreeList<Chunk_t>* fl) {}
981 983
982 #ifndef SERIALGC 984 #if INCLUDE_ALL_GCS
983 void do_list(AdaptiveFreeList<Chunk_t>* fl) { 985 void do_list(AdaptiveFreeList<Chunk_t>* fl) {
984 double coalSurplusPercent = _percentage; 986 double coalSurplusPercent = _percentage;
985 fl->compute_desired(_inter_sweep_current, _inter_sweep_estimate, _intra_sweep_estimate); 987 fl->compute_desired(_inter_sweep_current, _inter_sweep_estimate, _intra_sweep_estimate);
986 fl->set_coal_desired((ssize_t)((double)fl->desired() * coalSurplusPercent)); 988 fl->set_coal_desired((ssize_t)((double)fl->desired() * coalSurplusPercent));
987 fl->set_before_sweep(fl->count()); 989 fl->set_before_sweep(fl->count());
988 fl->set_bfr_surp(fl->surplus()); 990 fl->set_bfr_surp(fl->surplus());
989 } 991 }
990 #endif // SERIALGC 992 #endif // INCLUDE_ALL_GCS
991 }; 993 };
992 994
993 // Used to search the tree until a condition is met. 995 // Used to search the tree until a condition is met.
994 // Similar to TreeCensusClosure but searches the 996 // Similar to TreeCensusClosure but searches the
995 // tree and returns promptly when found. 997 // tree and returns promptly when found.
1132 double percentage; 1134 double percentage;
1133 public: 1135 public:
1134 setTreeSurplusClosure(double v) { percentage = v; } 1136 setTreeSurplusClosure(double v) { percentage = v; }
1135 void do_list(FreeList<Chunk_t>* fl) {} 1137 void do_list(FreeList<Chunk_t>* fl) {}
1136 1138
1137 #ifndef SERIALGC 1139 #if INCLUDE_ALL_GCS
1138 void do_list(AdaptiveFreeList<Chunk_t>* fl) { 1140 void do_list(AdaptiveFreeList<Chunk_t>* fl) {
1139 double splitSurplusPercent = percentage; 1141 double splitSurplusPercent = percentage;
1140 fl->set_surplus(fl->count() - 1142 fl->set_surplus(fl->count() -
1141 (ssize_t)((double)fl->desired() * splitSurplusPercent)); 1143 (ssize_t)((double)fl->desired() * splitSurplusPercent));
1142 } 1144 }
1143 #endif // SERIALGC 1145 #endif // INCLUDE_ALL_GCS
1144 }; 1146 };
1145 1147
1146 template <class Chunk_t, template <class> class FreeList_t> 1148 template <class Chunk_t, template <class> class FreeList_t>
1147 void BinaryTreeDictionary<Chunk_t, FreeList_t>::set_tree_surplus(double splitSurplusPercent) { 1149 void BinaryTreeDictionary<Chunk_t, FreeList_t>::set_tree_surplus(double splitSurplusPercent) {
1148 setTreeSurplusClosure<Chunk_t, FreeList_t> sts(splitSurplusPercent); 1150 setTreeSurplusClosure<Chunk_t, FreeList_t> sts(splitSurplusPercent);
1155 size_t hint; 1157 size_t hint;
1156 public: 1158 public:
1157 setTreeHintsClosure(size_t v) { hint = v; } 1159 setTreeHintsClosure(size_t v) { hint = v; }
1158 void do_list(FreeList<Chunk_t>* fl) {} 1160 void do_list(FreeList<Chunk_t>* fl) {}
1159 1161
1160 #ifndef SERIALGC 1162 #if INCLUDE_ALL_GCS
1161 void do_list(AdaptiveFreeList<Chunk_t>* fl) { 1163 void do_list(AdaptiveFreeList<Chunk_t>* fl) {
1162 fl->set_hint(hint); 1164 fl->set_hint(hint);
1163 assert(fl->hint() == 0 || fl->hint() > fl->size(), 1165 assert(fl->hint() == 0 || fl->hint() > fl->size(),
1164 "Current hint is inconsistent"); 1166 "Current hint is inconsistent");
1165 if (fl->surplus() > 0) { 1167 if (fl->surplus() > 0) {
1166 hint = fl->size(); 1168 hint = fl->size();
1167 } 1169 }
1168 } 1170 }
1169 #endif // SERIALGC 1171 #endif // INCLUDE_ALL_GCS
1170 }; 1172 };
1171 1173
1172 template <class Chunk_t, template <class> class FreeList_t> 1174 template <class Chunk_t, template <class> class FreeList_t>
1173 void BinaryTreeDictionary<Chunk_t, FreeList_t>::set_tree_hints(void) { 1175 void BinaryTreeDictionary<Chunk_t, FreeList_t>::set_tree_hints(void) {
1174 setTreeHintsClosure<Chunk_t, FreeList_t> sth(0); 1176 setTreeHintsClosure<Chunk_t, FreeList_t> sth(0);
1178 // Save count before previous sweep and splits and coalesces. 1180 // Save count before previous sweep and splits and coalesces.
1179 template <class Chunk_t, template <class> class FreeList_t> 1181 template <class Chunk_t, template <class> class FreeList_t>
1180 class clearTreeCensusClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> { 1182 class clearTreeCensusClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> {
1181 void do_list(FreeList<Chunk_t>* fl) {} 1183 void do_list(FreeList<Chunk_t>* fl) {}
1182 1184
1183 #ifndef SERIALGC 1185 #if INCLUDE_ALL_GCS
1184 void do_list(AdaptiveFreeList<Chunk_t>* fl) { 1186 void do_list(AdaptiveFreeList<Chunk_t>* fl) {
1185 fl->set_prev_sweep(fl->count()); 1187 fl->set_prev_sweep(fl->count());
1186 fl->set_coal_births(0); 1188 fl->set_coal_births(0);
1187 fl->set_coal_deaths(0); 1189 fl->set_coal_deaths(0);
1188 fl->set_split_births(0); 1190 fl->set_split_births(0);
1189 fl->set_split_deaths(0); 1191 fl->set_split_deaths(0);
1190 } 1192 }
1191 #endif // SERIALGC 1193 #endif // INCLUDE_ALL_GCS
1192 }; 1194 };
1193 1195
1194 template <class Chunk_t, template <class> class FreeList_t> 1196 template <class Chunk_t, template <class> class FreeList_t>
1195 void BinaryTreeDictionary<Chunk_t, FreeList_t>::clear_tree_census(void) { 1197 void BinaryTreeDictionary<Chunk_t, FreeList_t>::clear_tree_census(void) {
1196 clearTreeCensusClosure<Chunk_t, FreeList_t> ctc; 1198 clearTreeCensusClosure<Chunk_t, FreeList_t> ctc;
1250 fl->print_on(gclog_or_tty); 1252 fl->print_on(gclog_or_tty);
1251 _total_free += fl->count() * fl->size() ; 1253 _total_free += fl->count() * fl->size() ;
1252 total()->set_count( total()->count() + fl->count() ); 1254 total()->set_count( total()->count() + fl->count() );
1253 } 1255 }
1254 1256
1255 #ifndef SERIALGC 1257 #if INCLUDE_ALL_GCS
1256 void do_list(AdaptiveFreeList<Chunk_t>* fl) { 1258 void do_list(AdaptiveFreeList<Chunk_t>* fl) {
1257 if (++_print_line >= 40) { 1259 if (++_print_line >= 40) {
1258 FreeList_t<Chunk_t>::print_labels_on(gclog_or_tty, "size"); 1260 FreeList_t<Chunk_t>::print_labels_on(gclog_or_tty, "size");
1259 _print_line = 0; 1261 _print_line = 0;
1260 } 1262 }
1269 total()->set_coal_births( total()->coal_births() + fl->coal_births() ); 1271 total()->set_coal_births( total()->coal_births() + fl->coal_births() );
1270 total()->set_coal_deaths( total()->coal_deaths() + fl->coal_deaths() ); 1272 total()->set_coal_deaths( total()->coal_deaths() + fl->coal_deaths() );
1271 total()->set_split_births(total()->split_births() + fl->split_births()); 1273 total()->set_split_births(total()->split_births() + fl->split_births());
1272 total()->set_split_deaths(total()->split_deaths() + fl->split_deaths()); 1274 total()->set_split_deaths(total()->split_deaths() + fl->split_deaths());
1273 } 1275 }
1274 #endif // SERIALGC 1276 #endif // INCLUDE_ALL_GCS
1275 }; 1277 };
1276 1278
1277 template <class Chunk_t, template <class> class FreeList_t> 1279 template <class Chunk_t, template <class> class FreeList_t>
1278 void BinaryTreeDictionary<Chunk_t, FreeList_t>::print_dict_census(void) const { 1280 void BinaryTreeDictionary<Chunk_t, FreeList_t>::print_dict_census(void) const {
1279 1281
1284 1286
1285 FreeList_t<Chunk_t>* total = ptc.total(); 1287 FreeList_t<Chunk_t>* total = ptc.total();
1286 FreeList_t<Chunk_t>::print_labels_on(gclog_or_tty, " "); 1288 FreeList_t<Chunk_t>::print_labels_on(gclog_or_tty, " ");
1287 } 1289 }
1288 1290
1289 #ifndef SERIALGC 1291 #if INCLUDE_ALL_GCS
1290 template <> 1292 template <>
1291 void BinaryTreeDictionary<FreeChunk, AdaptiveFreeList>::print_dict_census(void) const { 1293 void BinaryTreeDictionary<FreeChunk, AdaptiveFreeList>::print_dict_census(void) const {
1292 1294
1293 gclog_or_tty->print("\nBinaryTree\n"); 1295 gclog_or_tty->print("\nBinaryTree\n");
1294 AdaptiveFreeList<FreeChunk>::print_labels_on(gclog_or_tty, "size"); 1296 AdaptiveFreeList<FreeChunk>::print_labels_on(gclog_or_tty, "size");
1306 - total->split_deaths() - total->coal_deaths()) 1308 - total->split_deaths() - total->coal_deaths())
1307 /(total->prev_sweep() != 0 ? (double)total->prev_sweep() : 1.0), 1309 /(total->prev_sweep() != 0 ? (double)total->prev_sweep() : 1.0),
1308 (double)(total->desired() - total->count()) 1310 (double)(total->desired() - total->count())
1309 /(total->desired() != 0 ? (double)total->desired() : 1.0)); 1311 /(total->desired() != 0 ? (double)total->desired() : 1.0));
1310 } 1312 }
1311 #endif // SERIALGC 1313 #endif // INCLUDE_ALL_GCS
1312 1314
1313 template <class Chunk_t, template <class> class FreeList_t> 1315 template <class Chunk_t, template <class> class FreeList_t>
1314 class PrintFreeListsClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> { 1316 class PrintFreeListsClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> {
1315 outputStream* _st; 1317 outputStream* _st;
1316 int _print_line; 1318 int _print_line;
1412 template class TreeList<Metachunk, FreeList>; 1414 template class TreeList<Metachunk, FreeList>;
1413 template class BinaryTreeDictionary<Metachunk, FreeList>; 1415 template class BinaryTreeDictionary<Metachunk, FreeList>;
1414 template class TreeChunk<Metachunk, FreeList>; 1416 template class TreeChunk<Metachunk, FreeList>;
1415 1417
1416 1418
1417 #ifndef SERIALGC 1419 #if INCLUDE_ALL_GCS
1418 // Explicitly instantiate these types for FreeChunk. 1420 // Explicitly instantiate these types for FreeChunk.
1419 template class TreeList<FreeChunk, AdaptiveFreeList>; 1421 template class TreeList<FreeChunk, AdaptiveFreeList>;
1420 template class BinaryTreeDictionary<FreeChunk, AdaptiveFreeList>; 1422 template class BinaryTreeDictionary<FreeChunk, AdaptiveFreeList>;
1421 template class TreeChunk<FreeChunk, AdaptiveFreeList>; 1423 template class TreeChunk<FreeChunk, AdaptiveFreeList>;
1422 1424
1423 #endif // SERIALGC 1425 #endif // INCLUDE_ALL_GCS